"big-O of log n"] time.  
This structure was invented in 1972 by Rudolph Bayer, and its height is no more than 2 lg (n+1) ["twice the base 2 log of n-plus-one"] if it contains n nodes.  A similar structure created by Adelson-Velsky and Landis is a type of this and shares the property that it may require up to two rotations per insertion and can insert or delete in O (lg n) ["big-O of log n"] time.  In it, no leaf may be more than twice as far from the root as any other, and every simple path from a node to a descendent contains the same number of nodes of the second namesake type.  FTP, name this type of nearly-balanced tree, of which the AVL tree is a type, and each of whose nodes contain a bit indicating which of two "colors" the node is.
This structure was invented in 1972 by Rudolph Bayer, and its height is no more than 2 lg (n+1) ["twice the base 2 log of n-plus-one"] if it contains n nodes.  
red-black tree (or symmetric binary B-tree; prompt on "B-tree" or "tree")