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.