Red-Black tree — properties, rotations + recoloring (conceptual understanding): Worked examples

This page is the drill hall for Red-Black tree insertion. The parent note explained the rules; here we hit every kind of situation an insertion can throw at you — from the trivial empty tree, through both mirror sides, both bend shapes, the recolor cascade, all the way up to a real-world map lookup and an exam twist.

Before any symbols: a Red-Black tree is a Binary Search Tree where each node also carries one bit of colour — red or black — and colours obey five rules so the tree can never grow more than twice as tall on one side as another. We repair broken rules with two tools: rotation (move nodes, keep order — see Tree Rotations) and recoloring (swap colours, move nobody).

Recall The four labels we reuse everywhere

When we insert a node $z$ (always coloured red), we name its relatives:

$z$ ::: the freshly inserted node, always red
$p$ ::: its parent
$g$ ::: its grandparent (parent of $p$ )
$u$ ::: its uncle (the other child of $g$ — the sibling of $p$ )

The scenario matrix

Every insertion that causes trouble falls into exactly one cell below. "Trouble" only ever means property 4 (a red node with a red child — "red-red"), because a red new node can never break the equal-black-count rule by itself.

#	Cell (scenario class)	Uncle colour	Shape of $g$ – $p$ – $z$	Fix	Terminates?
A	Empty tree	—	—	colour root black	yes
B	Parent is black	—	—	do nothing	yes
C	Uncle RED (left side)	red	any	recolor	loops up
D	Uncle RED cascade	red then red	any	recolor twice	loops up
E	Uncle BLACK, straight line, left-left	black/NIL	straight	recolor + 1 rotate	yes
F	Uncle BLACK, straight line, right-right (mirror of E)	black/NIL	straight	recolor + 1 rotate	yes
G	Uncle BLACK, bent, left-right (zig-zag)	black/NIL	bent	2 rotates + recolor	yes
H	Uncle BLACK, bent, right-left (mirror of G)	black/NIL	bent	2 rotates + recolor	yes
I	Real-world: `std::map` insert sequence	mixed	mixed	full sequence	yes
J	Exam twist: "which property first breaks?"	—	—	reasoning	yes

How to read the map figure below, arrow by arrow. The single orange box at the very top is where every insertion begins: you just placed a new red node $z$ . From it three navy arrows fan out — this is question 1 ("is there a parent, and is it red?"):

The left arrow goes to the violet box "no parent → A: root black" — you inserted into an empty tree.
The middle arrow goes to "parent BLACK → B: stop" — a red child under a black parent is legal, no repair.
The right arrow goes to the magenta box "parent RED → check uncle" — the only branch that has real work.

From that magenta box, two more arrows (labelled red and black) ask question 2, "what colour is the uncle?": the red arrow drops to "uncle RED → C/D: recolor", the black arrow drops to "uncle BLACK → check shape". Finally, from that box two arrows ask question 3, "straight or bent?": one to "straight → E/F: 1 rotate", one to "bent → G/H: 2 rot". So while working any example below, find the node you are stuck on, trace these arrows top-to-bottom answering the three questions in order, and the leaf box you land on is the exact matrix cell — and the exact worked example — you need.

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

Example A — the empty tree (cell A)

Worked example Insert

$50$ into an empty Red-Black tree. Forecast: Guess — what colour is the very first node, and why can't it stay red?

Step 1. BST-insert $50$ ; it becomes the root. Colour it red by our default rule. Why this step? We always insert red first — a red node can only break the easy property 4, never the hard equal-black-count property 5.

Step 2. Property 2 (root must be black) forces a recolour: $50$ → black. Why this step? Making the root black adds one black to every path equally, so no path count is disturbed. It is always safe.

Verify: One node, black, no children but two NIL leaves (both black by property 3). Every root-to-NIL path passes exactly two black nodes — the data node $50$ and the trailing NIL — so all paths tie → property 5 holds. No red-red → property 4 holds. ✓ Height $= 1$ (one data node), and the bound $2 lo g_{2} (1 + 1) = 2$ satisfies $1 \leq 2$ . ✓

Example B — black parent, nothing to do (cell B)

Example C — uncle is RED, pure recolor (cell C)

Worked example

$g = 10$ (black), $p = 5$ (red left), $u = 15$ (red right). Insert $3$ . Forecast: Uncle is red — will we rotate or just repaint? Guess before reading.

Step 1. $3 < 10$ left, $3 < 5$ left → $3$ red left-child of $5$ . Why this step? BST insert, default red.

Step 2. $p = 5$ (red) now has red child $3$ → red-red (breaks property 4). Look at uncle $u = 15$ : red. Why this step? The uncle's colour is the single fact that decides recolor vs rotate.

Step 3. Case 1 recolor: $p = 5 \to$ black, $u = 15 \to$ black, $g = 10 \to$ red. Set $z = 10$ , re-check upward. Why this step? Painting both children of $g$ black kills the red-red and keeps property 5: we added one black on each side of $g$ and removed one at $g$ , so every path's black count is unchanged.

Step 4. $z = 10$ is the root → property 2 → recolour $10 \to$ black. Done. Why this step? Root-black is always free.

Verify: Final tree $10$ (black) with $5$ (black), $15$ (black), and $3$ (red) under $5$ . Path $10 \to 5 \to 3 \to NIL$ : blacks ${10, 5, NIL} = 3$ . Path $10 \to 15 \to NIL$ : blacks ${10, 15, NIL} = 3$ . Equal. ✓ No red-red. ✓

Example D — the recolor cascade (cell D)

This is the "loops up" case: one recolor floats the problem higher, and we must fix it again. We start from a valid Red-Black tree (no rule broken) and only the insertion creates the violation.

Worked example Build the valid tree below, then insert

$4$ . Start (all rules hold): $20$ (black root); left child $10$ (black); right child $30$ (black); under $10$ : left child $5$ (red), right child $15$ (red). Insert $4$ .

Sanity check on the start tree: $10$ is black, so its two red children $5, 15$ do not break property 4 (red-red needs a red parent). Every root-to-NIL path has black count $3$ (e.g. $20 \to 10 \to 5 \to NIL = {20, 10, NIL}$ and $20 \to 30 \to NIL = {20, 30, NIL}$ ). Valid ✓.

Forecast: After the first recolor, node $10$ turns red under root $20$ . Does the fix stop there, or float higher? Guess.

Step 1. $4 < 20$ left, $4 < 10$ left, $4 < 5$ left → $4$ red left-child of $5$ . Why this step? BST insert, red.

Step 2. $p = 5$ (red) has red child $4$ → red-red (property 4). Uncle of $4$ = $15$ (other child of $g = 10$ ): red. Why this step? Uncle red → Case 1 recolor.

Step 3. Recolor: $5 \to$ black, $15 \to$ black, $g = 10 \to$ red. Set $z = 10$ . Why this step? Same balanced recolor as before; now re-examine $z = 10$ .

Step 4. New check at $z = 10$ (red): its parent is $20$ (black). Red-under-black — no violation. Stop. Why this step? The floated-up red only causes trouble if its parent is also red. Here $20$ is black, so the cascade ends after one hop.

Step 5. Root $20$ already black → property 2 fine.

Verify: Path $20 \to 10 \to 5 \to 4 \to NIL$ : blacks ${20, 5, NIL} = 3$ . Path $20 \to 10 \to 15 \to NIL$ : blacks ${20, 15, NIL} = 3$ . Path $20 \to 30 \to NIL$ : blacks ${20, 30, NIL} = 3$ . All equal → property 5 holds. ✓

Example E — black uncle, straight LEFT-LEFT line (cell E)

Worked example

$g = 30$ (black), $p = 20$ (red, left child), uncle = right child of $30$ = NIL (black). Insert $10$ .

Forecast: The three nodes lie on one straight left-leaning line. One rotation or two? Guess.

Step 1. $10 < 30$ left, $10 < 20$ left → $10$ red left-child of $20$ . Why this step? BST insert, red.

Step 2. $p = 20$ (red) has red child $10$ → red-red (property 4). Uncle = NIL → black (property 3). Line $30$ – $20$ – $10$ goes left-left → straight. Why this step? Black uncle rules out recoloring; straight line means we can rotate once.

Step 3. Recolor $p = 20 \to$ black, $g = 30 \to$ red. Why this step? We are about to lift $20$ to the top; it must become the new black subtree root while $30$ drops to red so black counts still balance.

Step 4. Right-rotate at $g = 30$ : $20$ rises, $30$ becomes its right child. Why this step? Rotating toward the heavy (left) side moves the tall path up, evening out heights. Order stays $10 < 20 < 30$ .

Verify: Result $20$ (black) with children $10$ (red), $30$ (red). Path $20 \to 10 \to NIL$ : blacks ${20, NIL} = 2$ . Path $20 \to 30 \to NIL$ : blacks ${20, NIL} = 2$ . Equal, no red-red. ✓

In the figure below, the left tree is the crooked "BEFORE" (all three nodes lean left); the orange arrow is our recolor-plus-right-rotate; the right tree is the tidy "AFTER" where $20$ (navy = black) sits atop two red children. Navy circles are black nodes, magenta circles are red — watch $20$ change from magenta to navy as it rises.

Example F — black uncle, straight RIGHT-RIGHT line (mirror of E, cell F)

Worked example Insert

$1, 2, 3$ into an empty tree. Forecast: This is E's mirror. Which way do we rotate now — left or right? Guess.

Step 1. Insert $1$ : root, coloured black (cell A). Why this step? First node is always root → property 2 forces black.

Step 2. Insert $2$ : $2 > 1$ right → red right-child of $1$ . Parent black → OK (cell B). Why this step? Red-under-black is legal (property 4 needs red-red), so nothing to fix.

Step 3. Insert $3$ : $3 > 1$ right, $3 > 2$ right → red right-child of $2$ . Red-red ( $2$ – $3$ , property 4). Uncle = left child of $1$ = NIL → black. Line $1$ – $2$ – $3$ right-right → straight. Why this step? Black uncle + straight line = single rotation.

Step 4. Recolor $p = 2 \to$ black, $g = 1 \to$ red. Why this step? Prepare $2$ as the new black subtree root.

Step 5. Left-rotate at $g = 1$ (mirror of E's right-rotate): $2$ rises, $1$ becomes its left child. Why this step? The heavy side is now the right, so we rotate left. Order $1 < 2 < 3$ preserved.

Verify: $2$ (black), children $1$ (red), $3$ (red). Path $2 \to 1 \to NIL$ : blacks ${2, NIL} = 2$ . Path $2 \to 3 \to NIL$ : blacks ${2, NIL} = 2$ . Equal, no red-red. Height $= 2$ , and $2 lo g_{2} (3 + 1) = 4 \geq 2$ . ✓

Example G — black uncle, bent LEFT-RIGHT (zig-zag, cell G)

The line bends, so a single rotation would not straighten it. We rotate twice.

Worked example

$g = 30$ (black), $p = 10$ (red, left child of $g$ ). Insert $20$ . Forecast: $20$ sits to the right of $p = 10$ , but $p$ is the left child of $g$ — a zig-zag. How many rotations? Guess.

Step 1. $20 < 30$ left, $20 > 10$ right → $20$ red right-child of $10$ . Why this step? BST insert, red.

Step 2. Red-red ( $10$ – $20$ , property 4). Uncle = right child of $30$ = NIL → black. Shape: $g$ left, then $z$ right → bent (left-right). Why this step? Bent + black uncle → Case 2 then Case 3.

Step 3. Left-rotate at $p = 10$ (Case 2): now $20$ sits above $10$ , giving a straight left-left line $30$ – $20$ – $10$ . Why this step? Rotations only clean up a straight line; this first rotate converts the zig-zag into cell E's shape. $z$ now points at $10$ .

Step 4. Now it's straight-left-left: recolor $20 \to$ black, $g = 30 \to$ red, then right-rotate at $g = 30$ (Case 3). Why this step? Identical to Example E — lift the new black root, drop $30$ to red.

Verify: $20$ (black) with children $10$ (red), $30$ (red). Path $20 \to 10 \to NIL$ : ${20, NIL} = 2$ ; Path $20 \to 30 \to NIL$ : ${20, NIL} = 2$ . Equal. ✓

The figure below is a three-panel film strip: leftmost is the bent zig-zag (note $10$ – $20$ kink); the first orange arrow is the "left-rotate at p" that straightens it into the middle panel (now a clean left-left line, exactly Example E's picture); the second orange arrow is the "recolor + right-rotate" that produces the balanced rightmost tree. Navy = black, magenta = red.

Example H — black uncle, bent RIGHT-LEFT (mirror of G, cell H)

Worked example

$g = 10$ (black), $p = 30$ (red, right child of $g$ ). Insert $20$ . Forecast: Mirror of G. Which rotation comes first now? Guess.

Step 1. $20 > 10$ right, $20 < 30$ left → $20$ red left-child of $30$ . Why this step? BST insert, red.

Step 2. Red-red ( $30$ – $20$ , property 4). Uncle = left child of $10$ = NIL → black. Shape: $g$ right, then $z$ left → bent (right-left). Why this step? Bent + black uncle → Case 2 (straighten) then Case 3 (rotate).

Step 3. Right-rotate at $p = 30$ (mirror of G's left-rotate): $20$ rises above $30$ , giving a straight right-right line $10$ – $20$ – $30$ . $z$ now points at $30$ . Why this step? Straighten the zig-zag into cell F's shape so a single clean rotation can finish it.

Step 4. Straight right-right: recolor $20 \to$ black, $g = 10 \to$ red, then left-rotate at $g = 10$ . Why this step? Exactly Example F now — lift the new black root $20$ , drop $10$ to red.

Verify: $20$ (black) with children $10$ (red), $30$ (red). Order $10 < 20 < 30$ preserved. Path $20 \to 10 \to NIL$ : blacks ${20, NIL} = 2$ . Path $20 \to 30 \to NIL$ : blacks ${20, NIL} = 2$ . Equal, no red-red. ✓ Two rotations total, mirroring G exactly.

Example I — real-world `std::map` insert run (cell I)

Worked example A C++ program does

std::map<int,int> m; then inserts keys $50, 25, 75, 10, 5$ in order. What is the final tree? (See std::map / TreeMap internals.) Forecast: Which insertion is the only one that triggers a rotation? Guess before working.

Step 1. Insert $50$ : root → black. (cell A) Why this step? Property 2 forces the first node black.

Step 2. Insert $25$ : $25 < 50$ left → red left-child of $50$ . Parent black → OK. (cell B) Why this step? Red-under-black is legal.

Step 3. Insert $75$ : $75 > 50$ right → red right-child of $50$ . Parent black → OK. (cell B) Why this step? Two red children under one black parent is allowed — no red-red.

Step 4. Insert $10$ : $10 < 50$ left, $10 < 25$ left → red left-child of $25$ . Red-red ( $25$ – $10$ ). Uncle = $75$ → red → recolor: $25 \to$ black, $75 \to$ black, $50 \to$ red; then property 2 forces $50 \to$ black again. (cell C) Why this step? Red uncle ⇒ pure recolor; root fixed back to black.

Step 5. Insert $5$ : $5 < 50$ left, $5 < 25$ left, $5 < 10$ left → red left-child of $10$ . Red-red ( $10$ – $5$ ). Uncle = right child of $25$ = NIL → black. Line $25$ – $10$ – $5$ left-left → straight → recolor $10 \to$ black, $25 \to$ red, right-rotate at $25$ . (cell E) Why this step? Black uncle + straight line ⇒ one rotation.

Verify — final tree: root $50$ (black); left subtree root $10$ (black) with children $5$ (red), $25$ (red); right child $75$ (black). Black-count on every root-to-NIL path:

$50 \to 10 \to 5 \to NIL$ : ${50, 10, NIL} = 3$
$50 \to 10 \to 25 \to NIL$ : ${50, 10, NIL} = 3$
$50 \to 75 \to NIL$ : ${50, 75, NIL} = 3$

All equal → property 5 holds; no red-red → property 4 holds. Exactly one rotation total (step 5), illustrating why RB is cheaper on updates than an AVL Tree would be. ✓

Example J — exam twist: "which property breaks first?" (cell J)

Worked example A student inserts a node and colours it

black (against the rule). In the tree $50$ (black), $25$ (black), $75$ (black), they insert $10$ as black left-child of $25$ . Which Red-Black property is the first to be violated, and by how much do black counts differ? Forecast: Property 4 (red-red) or property 5 (black-height)? Guess.

Step 1. No two reds are adjacent (we added a black), so property 4 is fine. Why this step? Red-red is impossible when the new node is black.

Step 2. Count blacks on the path through the new node vs a sibling path.

$50 \to 25 \to 10 \to NIL$ : ${50, 25, 10, NIL} = 4$ .
$50 \to 25 \to (other, NIL)$ : ${50, 25, NIL} = 3$ . Why this step? Property 5 demands equal black counts; here they differ.

Step 3. The counts differ by $4 - 3 = 1$ . Property 5 is the first (and only) broken rule, and it's off by exactly one black. Why this step? A stray black adds $1$ to just one branch's count — the very reason the parent note warns "never insert black."

Verify: This is precisely the [!mistake] "insert black to be safe" from the parent note, quantified: the damage is a black-height mismatch of $1$ on the affected subtree, the hardest property to repair. Inserting red instead would have left both counts at $3$ (the red node adds zero blacks). ✓

Recall One-line decision tree for any insertion

No parent → root black. Black parent → stop. Red parent + red uncle → recolor & loop up. Red parent + black uncle: straight → 1 rotate; bent → 2 rotates.

Recall Self-test

After recoloring in the red-uncle case, why might you have to repeat the fix? ::: Grandparent $g$ becomes red; if its parent is also red, a new red-red appears one level up, so you re-check from $z = g$ . Bent (zig-zag) case needs how many rotations, and why the first one? ::: Two; the first rotation straightens the line so the second (the real fix) has a clean straight $g$ – $p$ – $z$ to work on. Compared with an AVL Tree, why does RB rotate less? ::: RB allows a 2× path spread, so many fixes are pure recolors (no rotation); AVL's tight height-1 balance forces rotations more often. See Big-O Analysis.