= AVL tree
{c}
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.<Balanced binary trees in Cornell CS 2112>[AVL Trees and Rotations]{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 satisfies
$$
N(-1)=0,\quad N(0)=1,\quad N(h)=1+N(h-1)+N(h-2).
$$
This <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.
Back to article page
