AVL Trees

The previous lesson left us with a binary search tree that does everything in $O(h)$ time: magnificent when the tree is bushy, ruinous when a run of sorted insertions stretches it into a height-$\Theta (n)$ path. The fix is to refuse to let the tree get tall: pick a structural invariant that pins height to $O(\log n)$, and restore it after every update. The AVL tree, named for Adelson-Velsky and Landis (1962), is the oldest such scheme and the easiest to reason about, balancing by a direct height constraint at every node.¹

To talk about rebalancing we need one primitive, which the next lesson on balanced search trees treats in full: the rotation. A rotation rearranges three pointers to change a subtree's shape, and so its height, while preserving the BST ordering and running in $O(1)$ time. A right rotation at $y$ lifts its left child $x$ to the root and makes $y$ the right child of $x$; a left rotation is the inverse. That is all we need here: a cheap, order-preserving lever for trading height between siblings.

The AVL invariant

Define the height $h(x)$ of a node as the number of edges on the longest downward path to a leaf, with $h(\text{nil})=-1$. The balance factor is

and the invariant says exactly $bf(x)\in \{-1,0,+1\}$ for every node. We store $h(x)$ (or, equivalently, $bf(x)$) in each node and keep it current as the tree changes; both a search and an in-order walk ignore the field entirely, so a read-only operation on an AVL tree is just a BST operation.

A node with $bf=-2$ is left-heavy past tolerance, $bf=+2$right-heavy; these are the two illegal states an update can create, and the two we must repair.

Height is logarithmic

The invariant is worth what it buys, and what it buys is a logarithmic height bound. The cleanest argument is extremal: ask how few nodes an AVL tree of a given height can possibly contain. A sparse tree is the dangerous case, so if even the sparsest legal tree is bushy, all of them are.

The minimal-node trees are exactly the Fibonacci trees: the sparsest height-$h$ AVL tree is a root over a Fibonacci tree of height $h-1$ and one of height $h-2$. Because $1.44{\log }_{2}n<2{\log }_2(n+1)$, an AVL tree is provably shorter than the worst-case red-black tree of the same size, so its lookups touch fewer nodes. With $h=O(\log n)$ guaranteed, search, $\text{Insert}$, $\text{Delete}$, $\text{Min}$, and successor all run in $O(\log n)$ worst-case time.³

Insertion: rebalancing on the way up

We insert a key exactly as in a plain BST: descend to a leaf position and attach the new node. That can only push heights up along the single root-to-leaf path we just walked, so we retrace it upward, recomputing $h$ at each node. Let $z$ be the lowest node whose balance factor has become $\pm 2$. Its imbalance was caused by the new node landing in one of four positions relative to $z$, named by the two steps down the heavy path from $z$ toward the insertion:

• LL: left child left-heavy, a single right rotation at $z$.
• RR: right child right-heavy, a single left rotation at $z$.
• LR: left child right-heavy, a left rotation at the child, then a right rotation at $z$.
• RL: right child left-heavy, a right rotation at the child, then a left rotation at $z$.

Consider the LL case. Node $z$ has balance $-2$, its left child $y$ leans left, and the new node sits under $y$'s left child $x$. A single right rotation at $z$ lifts $y$ into $z$'s place, hangs $z$ as $y$'s right child, and rehomes $y$'s old right subtree as $z$'s new left subtree.

The LR case cannot be fixed by a single rotation: the heavy path zig-zags, so we first rotate the child to straighten it into an LL shape, then finish with the right rotation at $z$. Here $z$ has balance $-2$, its left child $y$ leans right, and the offending grandchild $x$ is $y$'s right child. A left rotation at $y$ lifts $x$ above $y$; the subtree is now left-left-heavy, and a right rotation at $z$ completes the repair, leaving $x$ as the new root.

The RR and RL cases are the left-right mirrors of LL and LR. For completeness, here is the RL double rotation, the mirror of the LR case just shown:

In every case the rebalanced subtree ends up with the same height it had before the insertion, which is the decisive fact:

So insertion is $O(\log n)$ to descend, $O(\log n)$ to walk back up adjusting heights, and at most a double rotation ($\le 2$ rotations) to repair: $O(\log n)$ overall. The dispatch is driven entirely by the stored heights:

Deletion: the same cases, but up the whole path

Deletion starts as in a BST, splicing out the node, or its in-order successor if it has two children, then retraces the path to the root updating heights, applying exactly the same four rotation cases at any node that reaches $|bf|=2$. The one difference is consequential. A rotation that repairs an insertion preserves the subtree's height, but a rotation that repairs a deletion can shrink the subtree by one. That shorter subtree may unbalance the node's parent, which may unbalance its parent, and so on. Deletion can therefore trigger up to $O(\log n)$ rotations cascading toward the root, though each is still $O(1)$, so the operation remains $O(\log n)$.³

AVL versus red-black

AVL and red-black trees both guarantee $O(\log n)$ height, but they sit at opposite ends of a tradeoff. The AVL height-difference invariant is strict: $h\le 1.44{\log }_{2}n$, noticeably shorter than red-black's $2{\log }_2(n+1)$, so AVL lookups are faster, the structure of choice for read-heavy workloads. The price is paid on updates: AVL trees track exact heights and may rotate to repair even small imbalances, whereas red-black trees tolerate looser balance and lean on cheap recolorings, doing fewer rotations per update. Roughly: AVL is more rigidly balanced and faster to search; red-black is cheaper to mutate, which is why it backs most standard-library ordered maps.⁴

Takeaways

• An AVL tree is a BST with the invariant that every node's two subtrees differ in height by at most $1$, i.e. its balance factor $bf(x)\in \{-1,0,+1\}$; each node stores its height (or balance).
• A minimal-node / Fibonacci-tree argument gives $N(h)=N(h-1)+N(h-2)+1$, so $N(h)=F_{h+3}-1$ and height $h\le 1.44{\log }_{2}n=O(\log n)$, hence all operations are worst-case $O(\log n)$.
• Insertion descends as a BST, retraces the path updating heights, and repairs the lowest unbalanced node with one of four cases, LL (right), RR (left), LR (left-then-right), RL (right-then-left), using $O(1)$ rotations, because the fix restores the subtree's prior height.
• Deletion uses the same four cases but its rotations can shrink a subtree, so the rebalancing may cascade up to the root, taking $O(\log n)$ rotations.
• Versus red-black trees: AVL is more rigidly balanced (shorter, faster lookups) but does more rotations per update.