A binary tree of which every subtree is search-optimal is called an AVL tree (height-balanced tree). Efficient algorithms for AVL trees are described in Knuth's The Art of Computer Programming chapter 6.2.3. In particular, you can insert a new element in $ O(\log n) $ time where $ n $ is the number of elements in the tree. Like Stanislav notes above, they are also described in Cormen–Leiserson–Rivest–Stein, Introduction to Algorithms second edition chapter 13-3.A binary tree of which every subtree is search-optimal is called an AVL tree (height-balanced tree). Efficient algorithms for AVL trees are described in Knuth's The Art of Computer Programming chapter 6.2.3. In particular, you can insert a new element in $ O(\log n) $ time where $ n $ is the number of elements in the tree. Like Stanislav notes above, they are also described in Cormen–Leiserson–Rivest–Stein, Introduction to Algorithms second edition chapter 13-3.
For searchFor search, these and related structures are called balanced trees.
Update: above is wrong, these and related structures are called balanced treessee comment of Michal R. Przybylek.