4.13.2 — Keeping Trees Balanced: Rotations, AVL & Red-Black

Chapter 4.13.1 ended on the problem: insert sorted data into a plain BST and you get a linked list. Since data arrives sorted constantly — by ID, by timestamp, by name — this is not an edge case, it is the default failure.

The fix is to notice the imbalance as it forms and repair it immediately, using an operation that changes the shape of the tree without changing its ordering. That operation is the rotation, and every balanced tree in existence is built from it.

1. The rotation: the one move everything is built from

A rotation takes a parent and one of its children and swaps which one is on top, re-hanging the middle subtree so the BST ordering rule still holds.

A right rotation. Node 20 moves up, 30 moves down to its right, and subtree B — which was 20's right child — becomes 30's left child. Read the in-order sequence off both pictures: A, 20, B, 30, C in each. The ordering is preserved exactly, which is why a rotation is always legal.

function rotateRight(root: AvlNode): AvlNode {   // (1)
  const pivot = root.left!;                      // (2)
  root.left = pivot.right;                       // (3)  subtree B changes parent
  pivot.right = root;                            // (4)  old root goes under the pivot
  updateHeight(root);                            // (5)  the lower node first
  updateHeight(pivot);
  return pivot;                                  // (6)  the new subtree root
}

1. Takes the current subtree root and returns the new one. The caller assigns the result back into whatever pointed here, which is the same "return the new subtree root" idiom as delete in 4.13.1.
2. The left child is what will move up. This is why a right rotation requires a left child to exist.
3. The only subtle line. Subtree B holds values between 20 and 30. It hangs off 20's right before the rotation and off 30's left after it. In both positions, "greater than 20 and less than 30" is exactly what belongs there, so the ordering survives.
4. Now 30 hangs under 20.
5. Heights must be recomputed bottom-up. root is now the lower of the two, so it must be updated before pivot, whose height depends on it. Getting this order wrong is a classic bug that produces a tree that looks right and reports wrong heights.
6. The caller needs the new top.

rotateLeft is this with left and right swapped. A rotation is O(1) — a handful of pointer writes, no traversal, no allocation. That is what makes rebalancing affordable.

2. AVL trees: keep every node's subtrees within one

The AVL tree (Adelson-Velsky and Landis, 1962, the first self-balancing BST) enforces one rule:

For every node, the heights of its left and right subtrees differ by at most 1.

That difference is the balance factor, height(left) − height(right), which must always be −1, 0 or +1. Each node stores its own height so the factor is computable in O(1).

class AvlNode {
  value: number;
  height = 0;                                  // (1)  leaf height is 0
  left: AvlNode | null = null;
  right: AvlNode | null = null;
  constructor(value: number) { this.value = value; }
}

const h = (n: AvlNode | null) => n === null ? -1 : n.height;   // (2)
const updateHeight = (n: AvlNode) => { n.height = 1 + Math.max(h(n.left), h(n.right)); };
const balance = (n: AvlNode) => h(n.left) - h(n.right);        // (3)

1. Storing the height is the extra memory AVL costs — one integer per node.
2. The empty tree at −1 makes a leaf come out at 0 with no special case, exactly as in 4.13.1.
3. Positive means left-heavy, negative means right-heavy.

Why "differ by at most 1" gives O(\log n) height. Ask the opposite question: what is the fewest nodes an AVL tree of height h can have? Call it N(h). Such a tree has a root, one subtree of height h−1, and — to be as sparse as possible while still legal — one of height h−2. So

N(h) = 1 + N(h-1) + N(h-2)

which is the Fibonacci recurrence. Fibonacci numbers grow like \phi^h where \phi \approx 1.618. So the sparsest possible AVL tree of height h still contains at least about \phi^h nodes, and inverting that, h \le 1.44 \log_2 n. The height can never exceed about 1.44 times the theoretical minimum, no matter what order you insert in. That bound is the entire guarantee.

The four rebalancing cases. After an insert, walk back up the path. At the first node whose balance factor reaches ±2, one of four situations holds, and each has a fixed repair.

Case	Shape	Repair
Left-Left	balance +2, left child leans left	one right rotation
Right-Right	balance −2, right child leans right	one left rotation
Left-Right	balance +2, left child leans right	rotate left on the child, then right on the node
Right-Left	balance −2, right child leans left	rotate right on the child, then left on the node

The two "straight" cases are one rotation. The two "zig-zag" cases need two, and the reason is worth seeing: a single rotation on a zig-zag shape just produces the mirror-image zig-zag and gets you nowhere. The first rotation straightens the kink into a straight line, and then the second rotation fixes the straight line.

function rebalance(node: AvlNode): AvlNode {
  updateHeight(node);
  const b = balance(node);
  if (b > 1) {                                                 // (1)  left-heavy
    if (balance(node.left!) < 0) node.left = rotateLeft(node.left!);   // (2)  Left-Right → straighten
    return rotateRight(node);                                  // (3)
  }
  if (b < -1) {                                                // (4)  right-heavy
    if (balance(node.right!) > 0) node.right = rotateRight(node.right!);
    return rotateLeft(node);
  }
  return node;                                                 // (5)  already fine
}

1. Balance factor +2 means too much on the left.
2. If the left child leans the other way, we have the zig-zag. One left rotation on the child converts Left-Right into Left-Left.
3. Now it is straight, so a single right rotation finishes it.
4. Mirror image.
5. Most nodes on the path need nothing, so this is the common exit.

Insertion needs at most one rebalance. Because a rotation at the lowest unbalanced node restores that subtree's original height, everything above it is instantly correct again. Deletion can need O(\log n) rebalances, because a delete can shrink a subtree's height, which can unbalance the parent, and so on up to the root. That asymmetry — one rotation to insert, up to log n to delete — is the practical difference between AVL and red-black.

3. Red-black trees: looser rule, cheaper writes, and what your language actually uses

AVL keeps the tree very tightly balanced, which makes reads fast and writes relatively expensive. Red-black trees relax the rule and get cheaper writes.

Each node carries one bit of colour, red or black, and five rules hold:

1. Every node is red or black.
2. The root is black.
3. Every leaf (conceptually, every null pointer) is black.
4. A red node's children are both black — no two reds in a row.
5. Every path from a node down to any of its null descendants contains the same number of black nodes.

Rules 4 and 5 do all the work, and here is why they bound the height. Rule 5 says the "black height" is identical on every path. Rule 4 says reds can never be adjacent, so on any path at most half the nodes are red. Therefore the longest possible path is at most twice the shortest possible path, and the height is at most 2 \log_2(n+1).

Compare the guarantees:

	AVL	Red-black
Height bound	~1.44 log n	~2 log n
Rebalance on insert	≤ 1 rotation	≤ 2 rotations
Rebalance on delete	up to log n rotations	≤ 3 rotations
Extra storage	an integer	one bit
Better for	read-heavy	write-heavy

The constant-bounded rotations on both insert and delete are red-black's real selling point, and it is why red-black won in practice. Almost every ordered container in a standard library is one:

• C++ std::map and std::set
• Java TreeMap and TreeSet
• The Linux kernel's process scheduler (CFS, Chapter 2.3), its virtual-memory area lookup, and its high-resolution timers
• Java's HashMap, for individual buckets that grow past 8 entries (Chapter 4.3)

You are essentially never asked to implement one in an interview — the insert-fixup has five cases and the delete-fixup has six, and reciting them proves nothing. What you are asked is what the guarantees are, why they hold, and when to pick one over AVL. Those are the parts above.

4. The alternatives that skip the bookkeeping

Two structures get the same O(\log n) result without maintaining an explicit invariant, and both are worth knowing because they show up in real systems.

Skip lists. Instead of a tree, a stack of linked lists. The bottom list holds every element in sorted order. Each higher list holds a random subset of the one below — a node is promoted to the next level up with probability 1/2, decided by a coin flip at insert time. Searching starts at the top and drops down whenever the next node overshoots, which skips large stretches in one hop, exactly like binary search.

The expected height is \log_2 n and every operation is O(\log n) expected — a probabilistic guarantee, not a worst-case one, though the probability of it being much worse decays exponentially. The payoff is that the code is dramatically simpler than a red-black tree, and that inserting only touches a local region, which makes lock-free concurrent versions far easier to write. Redis uses skip lists for its sorted-set type for exactly that reason.

Treaps. A BST by key and a heap by a randomly assigned priority, maintained together by rotations. Since the priorities are random, the resulting shape is the same as a randomly built BST — expected height 1.39 \log_2 n — regardless of the order the keys actually arrived in. The insight is elegant: you cannot control the insertion order, but you can add a second key that you do control, and randomise that instead.

Both are examples of trading a worst-case guarantee for a probabilistic one in exchange for much simpler code. That trade appears again in Chapter 4.29's probabilistic structures.

5. When to reach for a balanced tree at all

Chapter 4.3 gave the short answer: when you need order. Here is the full list of operations a balanced tree gives you that a hash map cannot give you at any price.

• Minimum and maximum — walk left or right to the end, O(\log n).
• Predecessor and successor — the next key below or above a given one.
• Range query — every key between two bounds, in O(\log n + k) for k results: find the lower bound, then walk in-order until you pass the upper bound.
• Sorted iteration — in-order traversal, O(n), no sorting step.
• Rank and select — "how many keys are below X" and "what is the k-th smallest", if each node also stores its subtree size.

That last one is the order-statistic tree, and the augmentation is instructive: store one extra number per node (the count of nodes in its subtree), maintain it in the rotation code, and two new queries become O(\log n). Augmenting a balanced tree with a summary of each subtree is a general technique, and Chapter 4.13.4's segment tree is the same idea taken to its conclusion.

The trade against a hash map is real and small: O(\log n) instead of O(1), which for a million entries is about 20 comparisons instead of 1. If you never ask an ordered question, use the hash map. If you ask even one, the tree is not a compromise — it is the only option.

Chapter 4.13.3 covers the case where the tree does not fit in memory at all, which changes the shape of the answer completely.

What the interviewer will push on

"Why does 'balance factor at most 1' give logarithmic height?" The Fibonacci argument: the sparsest AVL tree of height h has N(h) = 1 + N(h-1) + N(h-2) nodes, which grows like \phi^h, so h \le 1.44 \log_2 n. A candidate who can produce this has understood the guarantee; one who cannot has memorised the rule.

"Why do the zig-zag cases need two rotations?" Because a single rotation on a Left-Right shape produces a Right-Left shape — the mirror image of the same problem. The first rotation straightens the kink, the second fixes the resulting straight line.

"AVL or red-black — which and why?" The answer is about the workload: AVL is more tightly balanced so reads are slightly faster, red-black bounds rotations at a constant on both insert and delete so writes are cheaper. Then name what real systems chose and why — std::map, TreeMap and the Linux scheduler all use red-black.

"Why not just use a hash map?" The strong answer lists the operations a hash map cannot do at all, not the ones it does slower: min, max, predecessor, successor, range, sorted iteration. Then explain that this is exactly why database indexes are B+ trees rather than hash tables — WHERE created_at BETWEEN … AND … is a range query.

"A rotation changes the tree's shape. How do you know it stays a valid BST?" Read the in-order sequence before and after; it is identical. That is the invariant a rotation preserves, and it is the reason rotations are the only rebalancing move anyone uses.

One thing to volunteer: mention that a skip list gets the same expected bounds with far simpler code and much easier concurrency, and that Redis chose one for its sorted sets. That signals you know the textbook answer is not always the shipped answer.

Recall

• A rotation is O(1) and preserves the in-order sequence exactly, which is why it is the only legal reshaping move; every balanced tree is built from it.
• AVL keeps every node's balance factor in {−1, 0, +1}. The Fibonacci argument bounds the height at ~1.44 log₂ n. Insert needs at most one rebalance; delete can need O(\log n).
• The four cases are Left-Left, Right-Right, Left-Right and Right-Left; the two zig-zag cases need two rotations because one rotation only produces the mirror-image problem.
• Red-black trees use no-two-reds-in-a-row plus equal black-height to bound the longest path at twice the shortest, giving ~2 log n height with constant-bounded rotations on both insert and delete — which is why std::map, TreeMap and the Linux scheduler use them.
• Skip lists and treaps reach the same bounds probabilistically with far simpler code; Redis uses skip lists for sorted sets.
• Reach for a balanced tree when you need min/max, predecessor/successor, range queries or sorted iteration — things a hash map cannot do at all.

Self-test: Why does a rotation never break the BST ordering rule? · Derive the AVL height bound from N(h) = 1 + N(h-1) + N(h-2) · Why does AVL insert need at most one rebalance but delete can need log n? · Which two red-black rules bound the height, and how? · Name three queries a balanced tree answers that a hash map cannot answer at all.

Next: 4.13.3 asks what changes when the tree is too big for memory and every node access is a disk read — which is the question every database index is an answer to.