Red-Black tree — properties, rotations + recoloring (conceptual understanding): Visual walkthrough

Before we begin, three words must be earned, because the parent note used them freely and we will not.

We also need two words that describe how tall and how "black-heavy" a tree is. We define them the moment we draw them, not before.

Figure — Red-Black tree — properties, rotations + recoloring (conceptual understanding)

Everything below is a chain: many blacks ⟹ many nodes ⟹ tree can't be tall. Let's walk it.

Step 1 — Set the stage: what the coloring rules force onto a single path

WHAT. Take one root-to-NIL path and look only at it. Color its circles by the rules.

WHY. Before reasoning about the whole tree, understand the strongest constraint on the worst single path — that's what "height" measures. The whole bound is really a statement about one longest path.

PICTURE. In figure s02 the left path is all black — the shortest a path can be for a given black count. The right path alternates red, black, red, black — the longest a path can be for the same black count, because Property 4 (no red touches a red) forbids two reds in a row, so a red must be padded by a black on each side.

longest path length h \leq red pads each black 2 \cdot black nodes per path bh

Term by term: $h$ is the tallest trail; the factor $2$ is "one red allowed per black"; $bh$ is how many blacks every trail must contain. Rearranged: $bh \geq h /2$ . Keep this — it's Step 5's key.

Step 2 — The base case: the smallest possible subtree

WHAT. Ask: what is the emptiest thing a subtree can be? Just a NIL.

WHY. We are about to prove "black-height forces node-count" by induction. Induction needs a rock-bottom starting case that is obviously true. NIL is that floor.

PICTURE. Figure s03: a lone black NIL square. It has zero data nodes below and above it — it is the bottom.

Here $2^{bh} - 1$ is the quantity we claim counts the minimum data nodes forced by a black-height. At $bh = 0$ it predicts $0$ , which is exactly right. That's our foothold.

Step 3 — The inductive step: a "black-heavy" root must be a "fat" tree

WHAT. Assume the formula holds for anything shorter. Prove it for a node $x$ with black-height $bh (x)$ , using its two children.

WHY. This is the heart. We want to show that having many blacks per path is expensive — it forces the tree to contain many nodes. A tree can't be both black-heavy and skinny.

PICTURE. Figure s04: node $x$ at top, two subtrees hanging below. Each child, whatever its color, has black-height at least $bh (x) - 1$ : if the child is black it "uses up" one black (so its own paths have one fewer), and if the child is red it uses up none (so it keeps $bh (x)$ ). Either way, at least $bh (x) - 1$ blacks remain below each child.

Term by term: $2^{bh (x) - 1} - 1$ is the minimum nodes each child is forced to carry (one less black than $x$ ); the " $+ 1$ " is $x$ itself; the algebra $2 \cdot 2^{bh - 1} = 2^{bh}$ doubles it back up. Result: the same formula, one level taller. Induction complete.

Step 4 — Land the node-count law

WHAT. Apply Step 3 at the root. Let $bh$ = black-height of the root.

WHY. We now have a clean law connecting the tree's black-height to how many nodes it must contain. This is one of the two ropes we'll tie together.

PICTURE. Figure s05: the whole tree, with the guaranteed "minimum fatness" $2^{bh} - 1$ written across its base — a solid block of at least that many nodes.

Step 5 — Tie the two ropes: height is $O (lo g n)$

WHAT. Combine Step 1 ( $bh \geq h /2$ ) with Step 4 ( $lo g_{2} (n + 1) \geq bh$ ).

WHY. Step 1 says "tall path ⟹ many blacks." Step 4 says "many blacks ⟹ many nodes ⟹ big log." Chain them and the height gets trapped under a logarithm.

PICTURE. Figure s06: two inequalities drawn as arrows pointing at $bh$ from both sides, squeezing it, with the final bound below.

Term by term: on the left, $lo g_{2} (n + 1)$ is "how big the tree's log-size is"; in the middle, $bh$ is caught between two facts; on the right, $h /2$ is "half the tallest path" from Step 1. Multiplying across by $2$ frees $h$ . The height can never exceed twice the log of the size. That's $O (lo g n)$ — done.

Step 6 — Edge & degenerate cases (never leave a gap)

WHAT. Check the tree shapes where the argument feels like it might break.

WHY. The Contract: the reader must never hit a scenario we skipped. Bounds are only trustworthy if the boundary cases obey them too.

PICTURE. Figure s07 shows all four in a row.

Worked example Four boundary trees, each checked

(a) Empty tree, $n = 0$ . Root is a single NIL, $h = 0$ , $bh = 0$ . Bound: $h \leq 2 lo g_{2} (0 + 1) = 2 lo g_{2} 1 = 0$ . And $0 \leq 0$ . ✓

(b) One node, $n = 1$ . A single black root above two NILs. $h = 1$ . Bound: $2 lo g_{2} (2) = 2 \cdot 1 = 2$ , and $1 \leq 2$ . ✓ (Bound is loose — that's fine, it's an upper bound.)

(c) All-black path — the shortest possible longest path. Every node black. Here the longest path equals $bh$ , so $h = bh$ , not $2 bh$ . The $2 \times$ slack goes unused; the bound still holds with room to spare. ✓

(d) Maximal red padding — the tallest legal tree for its blacks. Red and black strictly alternate down the deepest path. Here $h = 2 bh$ exactly, hitting the $\leq 2 lo g_{2} (n + 1)$ ceiling as tight as it ever gets. You can never do worse than this, because Property 4 forbids adding one more red without a black between. ✓

The one-picture summary

Everything on this page is one arrow of implication, drawn end to end below.

Recall Feynman retelling — the whole walk in plain words

Picture a family tree where every person wears a red or black shirt, following two habits: a red-shirt never stands right above a red-shirt, and every straight walk down to the ground passes the same number of black shirts. First (Step 1) I look at one downward walk: since reds can't touch, the most reds I can squeeze in is one between each pair of blacks — so the walk is at most twice as long as its black-shirt count. Then (Steps 2–4) I flip it around: to fit that many black shirts on every walk, the tree is forced to be crowded — with $b$ blacks per walk, there must be at least $2^{b} - 1$ people. Then (Step 5) I glue the two facts: many blacks make the tree crowded, and a crowded tree of $n$ people can only afford about $lo g_{2} n$ blacks per walk — and since the height is at most twice the blacks, the height is at most about $2 lo g_{2} n$ . Finally (Step 6) I check the corners: the empty tree, the single person, the all-black skinny walk, and the maximally-striped tall walk — every one obeys the ceiling. So no legal shirt-coloring can ever grow a tree taller than twice the log of its size. That is why searching one is fast, and why std::map and TreeMap are built this way instead of on a plain Binary Search Tree.

Where this connects

Contrast with the tighter (height-differ-by-1) balancing of the AVL Tree — RB trades a little height for fewer rotations.
The $O (lo g n)$ conclusion is exactly the Big-O Analysis guarantee that makes RB operations cheap.
A Red-Black tree is the binary image of a 2-3-4 Tree — each 2-3-4 node maps to a small black-with-red cluster, which is another way to see why blacks stay balanced.