Balanced Search Trees

The previous lesson left us with a sharp problem. A binary search tree does everything in $O(h)$ time, which is glorious $\Theta (\log n)$ when the tree is balanced and catastrophic $\Theta (n)$ when it is not, and we cannot control the order in which keys arrive. A balanced search tree removes the dependence on luck. It maintains a structural invariant strong enough to force $h=O(\log n)$, and after every insertion or deletion it does a small amount of rebalancing to restore that invariant.¹ The guarantee becomes worst-case, not best-case: $O(\log n)$ per operation, on every input, forever.

Different balanced trees enforce different invariants. AVL trees bound the height difference of sibling subtrees, red-black trees color the nodes, and B-trees pack many keys per node, but they all share one mechanical primitive for reshaping the tree without disturbing its sorted order: the rotation.

Rotations: local surgery that preserves order

A rotation rearranges three pointers to change a tree's shape, and hence its height, while keeping the BST property intact. A right rotation at a node $y$ makes $y$'s left child $x$ the new subtree root, with $y$ becoming $x$'s right child; a left rotation is the exact inverse. The subtree that was in the middle (call it $T_2$) switches parents but stays between $x$ and $y$ in key order.

In both trees the sorted order is $T_1<x<T_2<y<T_3$ — a rotation never violates the BST property.² What it does change is height: rotating can pull a deep subtree up a level and push a shallow one down, which is precisely the lever a balanced tree pulls to repair itself.

A rotation touches only a constant number of pointers, so it runs in $O(1)$ time. Every balanced-tree rebalancing operation is built from a handful of rotations (plus, for red-black trees, recolorings) along a single root-to-leaf path, hence $O(\log n)$ work to repair the tree after an update.

Red-black trees: balance by color

A red-black tree is a BST in which every node carries one extra bit, its color — red or black.³ Five invariants on those colors squeeze the tree into logarithmic height:

1. Every node is either red or black.
2. The root is black.
3. Every leaf (the nil sentinel) is black.
4. If a node is red, then both its children are black (no two reds in a row).
5. For each node, every path from it down to a descendant leaf contains the same number of black nodes — its black-height.

Properties 4 and 5 are the engine. Property 5 says all root-to-leaf paths have the same number of black nodes; property 4 says reds cannot cluster, so reds can at most double a path's length by interleaving. Together they bound how lopsided the tree can get.

Why the height is $O(\log n)$

The argument is short and worth seeing, because it explains why the color rules take exactly this form. Let $bh(x)$ be the black-height of node $x$ (the number of black nodes on any path from $x$ down to a leaf, not counting $x$).

Now let $h$ be the tree's height. By property 4 at least half the nodes on any root-to-leaf path are black, so the root's black-height is at least $h/2$. Applying the lemma at the root with $n$ internal nodes,

So every operation that walks the tree (search, insert, delete, successor) runs in $O(\log n)$ worst-case time. After an insertion or deletion, the new node may violate property 4 (a red child of a red parent) or property 2/5; the tree repairs itself by recoloring and rotating up the path from the change toward the root. Each fix-up is $O(1)$ work, the path has length $O(\log n)$, and the loop terminates either by pushing the violation upward until it vanishes or by a final rotation. We will not work through every case of insert-fixup here; the point is the shape of the guarantee: bounded-height invariant plus $O(\log n)$ rotation-and-recolor repair equals worst-case logarithmic operations.

The most common fix-up is the easy one: when the newly inserted red node $z$ has a red parent and a red uncle $y$, we simply recolor — paint the parent and uncle black and the grandparent red — with no rotation at all. That repaints the local subtree to restore no two reds while preserving every path's black-height, but the grandparent is now red, so the violation may reappear one level up; we move $z$ to the grandparent and continue. Only when the uncle is black do we resort to one or two rotations, after which the loop ends.

The payoff is starkest on the worst possible input for a plain BST: keys arriving already sorted. A naive tree threads them into a single descending path of height $n-1$; the red-black invariants instead rebalance on the fly into a bushy tree of height $O(\log n)$, with every root-to-leaf path carrying the same black-height.

AVL trees reach the same $O(\log n)$ guarantee with a different invariant, namely that the heights of any node's two subtrees differ by at most $1$, enforced by rotations. AVL trees are more rigidly balanced (shorter, faster lookups) but do more rotations on updates; red-black trees are looser and rebalance more cheaply, which is why they back many standard-library ordered maps.⁴

B-trees: balance for the disk

Red-black and AVL trees minimize the number of nodes on a root-to-leaf path. But when the data lives on a disk or SSD, the cost that dominates is not comparisons but block transfers: reading one page from disk is millions of times slower than a memory comparison. A binary tree of $10^9$ keys has height $\approx 30$, meaning up to $30$ disk reads per search. That is the problem $\text{B-trees}$ solve.

A $\text{B-tree}$ of minimum degree $t\ge 2$ is a balanced search tree that is short and wide: each internal node holds between $t-1$ and $2t-1$ keys (kept sorted within the node) and correspondingly between $t$ and $2t$ children.⁵ Its defining structural rules:

• Every node holds between $t-1$ and $2t-1$ keys (the root may hold as few as $1$); a node with $k$ keys has exactly $k+1$ children.
• The keys in a node partition the key space, just as in a BST: child $i$ holds all keys between key $i-1$ and key $i$ of the node.
• All leaves are at the same depth, so the tree is perfectly height-balanced by construction.

Each node is sized to fill one disk block, so a single read brings in a whole fan-out's worth of keys. Because every node has up to $2t$ children, a B-tree holding $n$ keys has height

The fan-out $t$ sits in the denominator: making nodes wide makes the tree shallow. With $t$ on the order of a thousand keys per block, a tree of a billion keys has height $2$ or $3$, meaning two or three disk reads per search instead of thirty. Insertions and deletions keep all leaves at the same depth by splitting a full node (one with $2t-1$ keys) into two and pushing its median key up to the parent, or merging an underfull node with a sibling: local $O(t)$ restructuring that ripples at most up one root-to-leaf path.

B-trees (and their variant the B+-tree, which keeps all data in the leaves and links them for range scans) are the index structure databases and filesystems rely on for exactly this reason.

Takeaways

• A balanced search tree maintains a structural invariant that forces height $h=O(\log n)$, repairing it after each update so every operation is worst-case $O(\log n)$, not merely best-case.
• Rotations are the $O(1)$ primitive that reshapes a tree to change its height while preserving the BST property and sorted order.
• Red-black trees color nodes and enforce no-two-reds plus equal black-height; a counting argument shows $h\le 2{\log }_2(n+1)$, and fix-ups are $O(1)$ rotations/recolorings along one path.
• AVL trees reach the same bound with a stricter height-difference invariant: shorter trees, more rotations.
• $\text{B-trees}$ trade tall-and-thin for short-and-wide, packing $\Theta (t)$ keys per node so height is $O({\log }_{t}n)$, minimizing disk block transfers, the dominant cost for on-disk data.