Balanced Search Trees: Why Rotations Exist

A hash table gives constant-time lookup and no order. A binary search tree gives up some lookup speed to keep the keys sorted.

The rule is one invariant: for every node, all keys in its left subtree are smaller and all keys in its right subtree are larger. Searching becomes a sequence of comparisons that halves the candidate set each time, exactly like binary search over an array, except that insertion does not require shifting elements.

That invariant buys the operations a hash table cannot do. Walking the tree left-to-right visits keys in sorted order. Finding the smallest key is following left pointers to the end. A range query descends to one bound and walks forward. Every one of those is a natural consequence of the ordering.

Insert 1, 2, 3, 4, 5 into a plain binary search tree in that order. Every key is larger than the last, so every key goes right. You have built a linked list with extra pointers.

Lookup is now linear, and this is not a rare case. Sorted or nearly sorted input is the normal case in practice: timestamps, auto-increment ids, alphabetised names, data replayed from a sorted export.

insert 1..5 unbalanced:      balanced:
1                                3
 \                             /   \
  2                           2     4
   \                         /       \
    3                       1         5
     \
      4

The height of a tree is what its performance actually depends on. A tree of n nodes can have height anywhere from about log n to n, and nothing in the search-tree invariant prevents the bad end.

A rotation is the only structural edit a balanced tree needs. It rearranges three pointers among a parent and one child, changing the shape while preserving the search-tree ordering exactly.

Rotating left about a node pulls its right child up to take its place and pushes the node down to the left. The child's former left subtree, whose keys sit between the two nodes, is reattached where it still belongs. Nothing about the sorted order changes; only the height does.

This is why rotations matter: they are a constant-time operation that provably preserves correctness. Every balancing scheme in this lesson is built from them, and the schemes differ only in when they decide to apply one.

An AVL tree, the earliest self-balancing search tree, enforces a tight local rule: for every node, the heights of its two subtrees differ by at most one.

Each node stores that balance factor. After an insertion or deletion, the algorithm walks back up toward the root, and wherever the rule is violated it applies one or two rotations to restore it. The check is local and cheap, but it is applied everywhere.

The payoff is a genuinely short tree, with height bounded near 1.44 times the binary logarithm of n. That makes AVL trees excellent for lookup-dominated workloads. The cost is that this strictness triggers rotations more often on writes, because a small imbalance anywhere is enough to demand repair.

A red-black tree colours each node red or black and enforces two rules that matter: no red node has a red parent, and every path from the root down to a leaf passes through the same number of black nodes.

Those rules do not force the tree to be as short as an AVL tree. What they force is that the longest root-to-leaf path is at most twice the shortest, which as CLRS shows bounds the height at 2 log(n+1). That is still logarithmic, just with a larger constant.

The trade is deliberate. Because the constraint is weaker, an insertion or deletion needs fewer rotations to repair, and much of the fixing can be done by recolouring alone. Red-black trees are the common default in standard libraries for that reason: Java's TreeMap, C++'s std::map, and the Linux kernel's scheduler all use them.

Both are logarithmic, so the choice is about constants and workload shape.

The honest summary is that for most application code the difference is not measurable, and you should use whichever your standard library provides. The distinction becomes real when the workload is lopsided: heavy reads favour AVL, heavy mutation favours red-black.

Everything above assumes a comparison costs about the same as following a pointer. On disk, that assumption collapses.

Reading from storage happens in pages, typically 4 to 16 kilobytes at a time. A binary tree over a million keys has a height around 20, so a lookup could mean 20 page reads, and each one is orders of magnitude slower than a comparison in memory. The tree is balanced and still far too tall.

A B-tree fixes the mismatch by widening the node. Instead of one key and two children, a node holds hundreds of keys and hundreds of children, sized to fill one page. Height collapses accordingly: with a branching factor of 100, a million keys fit in a tree of height 3. The same balancing idea applies, but the unit of work is a page rather than a pointer. The db-btree-indexes lesson covers how storage engines build on this.

Balanced trees also appear as a safety net rather than a primary structure.

The previous lesson noted that OpenJDK's HashMap converts an over-full bucket into a red-black tree once it holds 8 entries, given a table of at least 64 buckets, and converts back when it shrinks to 6. That is a direct application of what this lesson establishes: the tree is slower than a short list in the common case, which is why the threshold exists, but its logarithmic bound is what stops an adversary from making one bucket linear.

It is a useful pattern to recognise. Trees are often chosen not because they are fastest on average, but because they have a floor. A structure with a good average and a terrible worst case can be paired with one that guarantees a bound.

You rarely implement one, so the skill is knowing what your library gives you.

A sorted map or set (TreeMap, std::map, SortedDict) is a balanced search tree. Reach for it when you need any ordered operation: floor and ceiling lookups, range scans, ordered iteration, or repeatedly finding the smallest remaining key.

Two gotchas are worth carrying. First, the comparison function is part of the structure's correctness: an inconsistent comparator, one that says a is less than b and also b is less than a, corrupts the tree silently rather than throwing. Second, pointer-based trees have poor locality compared with arrays, so for small collections a sorted array with binary search often wins outright despite the identical asymptotics.