 AVL tree

An AVL tree is a binary search tree in which the left and right subtree heights differ by at most one at every vertex. The ordering invariant supports directed search; the extra height condition prevents the long chains that make an unbalanced binary search tree slow. Tree rotations repair the shape while preserving key order.^[ref]

Inserting keys 3,2,1 into an ordinary binary search tree produces a chain. A right tree rotation at three makes two the root with children one and three. For a height proof, count edges and set the empty-tree height to $-1$. The minimum vertex count satisfiesThis Fibonacci sequence growth gives height of a binary tree $O(\log n)$, hence logarithmic worst-case search, insertion and deletion time complexity. Deletion may require repairs at several ancestors.