Balanced trees: the red-black guarantee

The problem balance solves

The previous lesson left us with a landmine: a plain BST built from sorted input degenerates into a height-$(n-1)$ chain, and every operation collapses to $\Theta(n)$. A balanced BST fixes this by keeping the height $O(\lg n)$ *no matter the insertion order*, so all operations stay $O(\lg n)$ in the worst case. A red-black tree is the workhorse balanced BST: a BST with one extra color bit (red or black) per node, plus rebalancing logic on insert and delete.

For this exam you need the *guarantee* and *why it holds* — not the memorized fixup cases. So this lesson is deliberately overview-only.

The five red-black properties

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, both its children are black (no two reds in a row on any path).
5. For every node, all simple paths down to descendant leaves contain the same number of black nodes (this count is the node's *black-height*).

Why these five force O(lg n) height

Look at any root-to-leaf path. Property 4 forbids consecutive red nodes, so at most *half* the nodes on the path can be red — meaning at least half are black. Property 5 says every such path has the same number of black nodes. So the longest possible path (alternating red/black) is at most twice the shortest (all black). That bounded ratio is the whole game.

Formally (Lemma 13.1): the subtree at a node of black-height $bh$ holds at least $2^{bh}-1$ internal nodes, and since black-height is at least $h/2$, you get $n \ge 2^{h/2}-1$, i.e.

$$h \le 2\lg(n+1) = O(\lg n).$$

Because every BST operation is $O(h)$ (Lesson 3.2), this single bound delivers $O(\lg n)$ worst-case SEARCH, MINIMUM, MAXIMUM, SUCCESSOR, PREDECESSOR, INSERT, and DELETE.

Rebalancing: rotations are O(1), and there are O(1) of them

Insert and delete restore the properties with rotations — local $O(1)$ pointer twists (LEFT-ROTATE, RIGHT-ROTATE) that *preserve the BST ordering* while reshaping the tree — plus recolorings. The headline numbers: RB-INSERT does at most 2 rotations, RB-DELETE at most 3, each plus $O(\lg n)$ recolorings, for $O(\lg n)$ total. That constant rotation bound is why red-black trees power Java's TreeMap, C++'s std::map, and the Linux kernel's scheduler — modifications complete in predictable, near-constant structural work.

Worked example — the doubling argument, concretely

Take a red-black tree with black-height 3 at the root. Lemma 13.1 says it holds at least $2^3 - 1 = 7$ internal nodes. The shortest root-to-leaf path is 3 nodes (all black); the longest is at most 6 (black-red-black-red-black-red). For $n = 10^9$ keys, the bound gives $h \le 2\lg(10^9 + 1) \approx 60$ — so any operation touches at most ~60 nodes, versus a billion for a degenerate chain. *That* is the difference between instant and timeout, and you derived it from five color rules, not from any rotation case.