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

(a) Legal. Root is black (property 2 — root black). Reds $4,12$ have only NIL (black) children, so no red-red (property 4). Every path is $8\to 4\to \text{NIL}$ or $8\to 12\to \text{NIL}$: each has exactly one black node ($8$) plus the NIL, so black counts match (property 5). ✅ (b) Illegal — property 2. The root $8$ is red. Property 2 demands the root be black. (c) Illegal — property 4. $4\text{(R)}$ has child $2\text{(R)}$ — two reds in a row (red-red).

Walk a path root → down to NIL, counting black nodes below the start (we exclude the root itself by definition, but count the terminal NIL). Path $10\to 5\text{(R)}\to \text{NIL(B)}$: black nodes below root = just the NIL = 1. Path $10\to 20\text{(B)}\to \text{NIL(B)}$: black nodes below root = $20$ and NIL = 2.

These disagree → this tree actually violates property 5 (equal black counts). Trick question: a valid RB tree could not look like this. If you were only asked "count black-height" you must first notice it's not well-formed. The consistent value would require both paths equal. ✅ (Lesson: black-height is only defined when property 5 holds.)

• (a) Case 1. Red uncle ⇒ pure recolour, push problem up. No rotation.
• (b) Case 3. NIL counts as black (property 3), uncle is black, and the path is a straight line ⇒ single rotation at $g$ + recolour, terminates.
• (c) Case 2. Black uncle but the shape is a zig-zag (inner grandchild) ⇒ first rotate at $p$ to straighten into Case 3.

Insert $10$ as red left child of $20$ (BST: $10<30$, $10<20$). Red-red between $20$ and $10$. Uncle $u=40$ is red ⇒ Case 1. Recolour: $p=20\to \text{black}$, $u=40\to \text{black}$, $g=30\to \text{red}$. Set $z=30$ and re-check upward; since $30$'s parent is black, the loop stops. Final: $10\text{(R)},20\text{(B)},40\text{(B)},30\text{(R)}$.

• Insert $1$: it's the root ⇒ black (property 2). Tree: $1\text{(B)}$.
• Insert $2$: $2>1$, red right child. Parent $1$ is black ⇒ no violation.
• Insert $3$: $3>2$, red right child of $2$. Red-red ($2$–$3$). Uncle = left child of $1$ = NIL = black. Line $1\to 2\to 3$ is straight-right ⇒ Case 3.
  • Recolour $p=2\to \text{black}$, $g=1\to \text{red}$.
  • Left-rotate at $g=1$: $2$ rises to the top with children $1$ and $3$.
• Final: $2\text{(B)}$, left $1\text{(R)}$, right $3\text{(R)}$.

Read the figure, don't just look at it. In the drawing, node $2$ is the dark, cyan-ringed circle at the top — the cyan ring is my visual code for black. Nodes $1$ and $3$ are the solid amber circles below it — amber is my code for red. Now trace the two downward paths with your finger: root $2\to 1\to$ NIL, and root $2\to 3\to$ NIL. On each path you pass through exactly one black node (the root $2$) before hitting the black NIL — that visual symmetry is precisely what property 5 (equal black counts) demands, and the amber annotation arrow points at $2$ to mark that shared single black node. Because $1$ and $3$ are both red leaves with only black NIL children, no red touches another red, so property 4 holds too. The whole tree is just 1 edge tall on both sides — the figure shows how the Case-3 rotation converted the lopsided stick $1\to 2\to 3$ into this balanced fan.

Height = 1 edge (root $2$ to leaf $1$ or $3$). Both paths pass exactly one black node ($2$) → property 5 ✅; no red-red → property 4 ✅.

Using the level convention above (root = level 1, children = level 2, grandchildren = level 3): The root (level 1) must be black (property 2). To avoid red-red (property 4), reds cannot touch. Colour the root black, both level-2 nodes (the root's direct children) red, and all four level-3 nodes (the leaves) black. Check property 5: every root→NIL path is level-1(B) → level-2 red → level-3 leaf(B) → NIL(B) = 2 black data nodes + NIL, equal on all four paths. ✅ Could we instead make the level-3 leaves red? Then their parents (level 2) must be black — which is fine — again giving 4 reds, also valid. But we cannot make level 2 and level 3 both red at once: a level-2 node and its level-3 child would be adjacent reds (red-red, property 4). So the maximum is 4 reds, sitting entirely on one level — all of level 2, or all of level 3, never mixing across adjacent levels.

• $10$: root ⇒ $10\text{(B)}$ (property 2).
• $20$: red right child of $10$. Parent black, OK.
• $30$: red right of $20$. Red-red, uncle NIL(B), straight line ⇒ Case 3: recolour $20\to$B, $10\to$R; left-rotate at $10$. Now $20\text{(B)}$ with children $10\text{(R)},30\text{(R)}$.
• $15$: BST path $15<20$ → left to $10$; $15>10$ → right of $10$. Insert red. Parent $p=10\text{(R)}$ → red-red. Grandparent $g=20$, uncle $u=30\text{(R)}$ → Case 1 recolour: $p=10\to$B, $u=30\to$B, $g=20\to$R. Set $z=20$. $20$ is the root ⇒ force black (property 2).
• Final: $20\text{(B)}$; left $10\text{(B)}$ with red right child $15\text{(R)}$; right $30\text{(B)}$.

Read the figure, don't just look at it. The black root $20$ sits alone at the top level. Below it, the two dark cyan-ringed circles $10$ and $30$ are the black children (cyan ring = black). The one solid amber circle, $15$, is the red node — and notice where it hangs: it is the right child of $10$, i.e. it leans back toward its grandparent $20$, which is what "inner grandchild" means. The amber annotation arrow labels exactly that. Now do the property-5 finger-trace on all three downward paths: (i) through the empty left of $10$ you pass $10$(B) then NIL(B) = 2 blacks; (ii) through $15$ you pass $10$(B), then $15$(R) counts nothing, then NIL(B) = 2 blacks; (iii) through $30$ you pass $30$(B) then NIL(B) = 2 blacks. All three read the same "2" — the cyan caption states this, and it's the whole reason the tree is legal after two different fixups (a Case 3 then a Case 1) chained back to back.

Check property 5: path to leftmost NIL (under $10$): blacks = $10$,NIL = 2. Path through $15$: $10$(B),NIL = 2. Path to $30$: $30$(B),NIL = 2. All equal ✅. No red-red ✅.

Reconciling the formula with our definition first. Our $bh(x)$ counts the terminal NIL but not $x$. The parent note's induction result "a subtree of black-height $b$ has $\ge 2^b-1$ internal nodes" counts only the data (internal) nodes below $x$ and treats each NIL as contributing 0 data nodes. So the two are consistent: a black-height of $b$ means $b$ black nodes on a path (NIL included), and among the data nodes that forces at least $2^b-1$ of them.

Minimum — for $b=2$: $2^2-1=3$ internal nodes. (Shape: an all-black perfect tree of 3 data nodes; each path has $10\text{(B)}$-style black nodes plus the NIL, giving 2 blacks.)

Maximum — why height can reach $2\cdot bh$. Property 4 (no red-red) says between any two red nodes on a path there is at least one black. So the densest legal path alternates black, red, black, red, … A path with $bh$ black nodes can therefore interleave up to $bh$ red nodes between and around them — doubling the node count. That means the maximum real height (in levels of data nodes) is $2\cdot bh$; here $2\cdot bh=4$ levels.

Why a perfect (completely filled) binary tree maximises node count for a fixed height. Fix the maximum number of levels at $H=2\cdot bh=4$. A binary node has at most 2 children, so level $k$ can hold at most $2^{k-1}$ nodes (level 1: $2^0=1$ node, level 2: $2^1=2$, level 3: $2^2=4$, level 4: $2^3=8$). Any tree limited to $H$ levels therefore has at most ${\sum }_{k=1}^H{2}^{k-1}$ nodes, and this bound is reached exactly when every level is completely filled — that filled-to-the-brim tree is precisely the perfect binary tree. Leaving any slot empty only removes nodes, never adds them, so no other shape of the same height can beat it. Summing the geometric series: ${\sum }_{k=1}^H{2}^{k-1}=2^H-1=2^{2\cdot bh}-1=2^4-1=15.$

So the range is $3\le n\le 15$.

Strategy. Property 5 forces every root→NIL path to carry the same number of black nodes, say $bh$. So to make one path longer than another, the extra nodes on the long path must all be red (red nodes add length but not to the black count). Property 4 forbids two reds touching, so on the long path reds must alternate with blacks: the longest a path can get is black, red, black, red, …, exactly $bh$ blacks and $bh$ reds = $2\cdot bh$ nodes. The shortest is all black = $bh$ nodes. Ratio $=2\cdot bh/bh=2$. To hit the ratio exactly we just build both extremes in one tree with the same $bh$.

We use $bh=2$ (2 black nodes per path, NIL counted). Target: a short side that is all-black (2 data blacks) and a long side that alternates to 4 data nodes (2 blacks + 2 reds).

Concrete final tree (all colours given):

• Root $40\text{(B)}$.
• Right (short) side: one node $60\text{(B)}$, whose children are both NIL.
• Left (long) side: $20\text{(B)}$; $20$'s left child $10\text{(R)}$; $10$'s left child $5\text{(B)}$; $5$'s children are NIL. ($20$'s right child and $10$'s right child are NIL.)

Verify property 5 — count black data nodes to every NIL:

• Short path $40\text{(B)}\to 60\text{(B)}\to \text{NIL}$: blacks = $40,60$ = 2 ✅
• Long path $40\text{(B)}\to 20\text{(B)}\to 10\text{(R)}\to 5\text{(B)}\to \text{NIL}$: blacks = $40,20,5$ … that's 3, which does not match the short side's 2. ❌

That mismatch is exactly the counting error to avoid — the extra black $5$ raised the count. Fix it by making the deepest data node red, so the long side alternates $B,B,R$? No — two blacks then a red still gives more blacks than the short side. The clean fix is to thin the short side's blacks to match by giving both sides black-height 2 while alternating the long side. Corrected final tree:

• Root $40\text{(B)}$.
• Right (short) side: $60\text{(B)}$ with NIL children. Short path blacks: $40,60$ = 2 ✅. Path length in data nodes: $40,60$ = 2.
• Left (long) side: $20\text{(B)}$; left child $10\text{(R)}$; and to keep the black count at 2 without adding a third black, $10$'s children are NIL. Long path blacks: $40,20$ = 2 ✅. But this path is only $40,20,10$ = 3 data nodes, giving ratio $3/2$, not $2$.

Reaching exactly $2\times$ needs $bh$ large enough to alternate fully. With $bh=2$ the longest alternating path is $B,R,B,R=4$ data nodes and the shortest is $B,B=2$ — ratio exactly $2$. So the alternating side must start with the root's black child then a red, then a black, then a red. Final valid tree that achieves it:

• Root $40\text{(B)}$.
• Right (short) side: internal node $60\text{(B)}$; its two children are NIL. Short path: $40\text{(B)}\to 60\text{(B)}\to \text{NIL}$ = 2 black data nodes, 2 data nodes total.
• Left (long) side: $20\text{(B)}$; $20$'s left child $10\text{(R)}$; $10$'s left child $5\text{(B)}$; $5$'s left child $2\text{(R)}$; $2$'s children NIL (all other missing children NIL).
  • Long path: $40\text{(B)}\to 20\text{(B)}\to 10\text{(R)}\to 5\text{(B)}\to 2\text{(R)}\to \text{NIL}$.
  • Blacks on it: $40,20,5$ = 3. Short side blacks: $40,60$ = 2. Still unequal.

The honest resolution: you cannot mix a 1-black short side with a fully-alternating long side and keep the root itself on both paths, because the root's single blackness is shared. The correct fully-valid construction keeps the common blacks equal by using the same $bh$ on both sides and putting the reds only on the long side. Here it is, checked once and for all with $bh=2$:

• Root $40\text{(B)}$ — lies on both paths, contributes 1 black to each.
• Short side: $60\text{(B)}$ (leaf). Path blacks below root: $60$ + NIL's node? NIL is black but is not a data node — for property 5 we count black nodes including NIL. Blacks on short path = $40,60,\text{NIL}$ = 3.
• Long side: $20\text{(R)}$; its child $10\text{(B)}$; $10$'s child $5\text{(R)}$; $5$'s child $3\text{(B)}$; $3$'s children NIL.
  • Long path: $40\text{(B)}\to 20\text{(R)}\to 10\text{(B)}\to 5\text{(R)}\to 3\text{(B)}\to \text{NIL(B)}$.
  • Blacks (including NIL): $40,10,3,\text{NIL}$ = 4. Short side gave 3. Off by one.
  • Add one black to the short side: make $60$ have a black child $70\text{(B)}$. Short path $40\text{(B)}\to 60\text{(B)}\to 70\text{(B)}\to \text{NIL}$ = blacks $40,60,70,\text{NIL}$ = 4 ✅ = long side.

Final valid tree (this one is correct — all counts verified):

• Root $40\text{(B)}$.
• Short side: $60\text{(B)}\to 70\text{(B)}$ (a straight all-black chain; $60$'s left and $70$'s children are NIL).
  • Path: $40,60,70,\text{NIL}$. Data nodes on path (excluding NIL) = $40,60,70$ = 3 nodes. Blacks incl. NIL = 4.
• Long side: $20\text{(R)}\to 10\text{(B)}\to 5\text{(R)}\to 3\text{(B)}$ ($3$'s children NIL).
  • Path: $40,20,10,5,3,\text{NIL}$. Data nodes on path = $40,20,10,5,3$ = 5 nodes. Blacks incl. NIL = $40,10,3,\text{NIL}$ = 4.

Hmm — $5$ data nodes vs $3$ is ratio $5/3$, not $2$. The mismatch keeps appearing because the shared root sits on both paths. Clean conclusion, stated exactly the way CLRS states the 2× bound: the bound compares the number of blacks on the shortest path to the total length of the longest path. The shortest possible path from the root is all black with $bh$ black nodes; the longest possible path alternates and has $2\cdot bh$ nodes. These two extremes need not coexist as literal siblings in one tiny tree — the theorem bounds the ratio between the extreme cases a valid tree may reach. The tightest single valid tree that displays both extremes at once is:

• Root $40\text{(B)}$, $bh=2$.
• Short branch = all black: $40\text{(B)}\to 30\text{(B)}\to \text{NIL}$? That is only 2 nodes. Pair it against
• Long branch = alternating with the same black count $bh=2$: $40\text{(B)}\to 50\text{(R)}\to 60\text{(B)}\to \text{NIL}$ = 3 data nodes, blacks $40,60,\text{NIL}$ = 3. Short branch $40,30,\text{NIL}$ blacks = 3. Equal ✅. Ratio of lengths $3/2$.

To force the ratio to a clean 2, we scale $bh$ up. Canonical exact-2× tree, $bh=3$:

• Short branch (all black): $B\to B\to B\to \text{NIL}$ = 3 data nodes, 4 blacks incl. NIL.
• Long branch (fully alternating, same 4 blacks incl. NIL): $B\to R\to B\to R\to B\to R\to \text{NIL}$ = 6 data nodes.
• $6/3=2$ exactly, both branches carry the identical black count (3 data blacks + NIL = 4), reds never touch (property 4 ✅), root black (property 2 ✅). This is a fully legal RB tree whose longest path is exactly twice its shortest. ∎

Why we can't beat 2×: each extra node on the long branch must be red (adding a black would break property 5's equal count), and reds cannot be adjacent (property 4), so at most every other node is red — capping the long branch at $2\times$ the all-black short branch. Achievable and un-beatable: the bound is tight.

RB — capped at 2 rotations per insert, always. After a BST insert we only ever run the fixup loop. Case 1 (red uncle) does zero rotations — it recolours and moves $z$ up. Only Case 2 + Case 3 rotate, and together they fire at most twice on a single insert, after which the loop terminates. So no matter how tall the tree, one insert costs $\le 2$ rotations $=O(1)$. Over all $n$ inserts: $\le 2n=O(n)$ rotations total. See Big-O Analysis and Tree Rotations.

AVL — a single rebalance can trigger a chain of rotations up the tree. AVL keeps every node's two subtree heights within $1$. When an insert makes some node's balance factor hit $\pm 2$, you rotate there. That rotation can change the height of the rebalanced subtree, which in turn can violate the balance factor of the node above it, forcing another rotation — and this can cascade all the way up the root path. Because the tree is height $O(\log n)$, that cascade is at most $O(\log n)$ rotations on a bad insert. (This is exactly why AVL's premise here is that a single insert may not be $O(1)$ rotations.) Contrast with AVL Tree: AVL's stricter invariant (heights differ by $\le 1$) is what forces it to propagate rebalancing further than RB's looser "$\le 2\times$ path" invariant does.

Answer: RB total rotations for $n$ sorted inserts $=O(n)$, with $\le 2$ per insert; a worst-case AVL insert can incur $O(\log n)$ rotations because rotations propagate up the height-invariant chain. This capped-rotation guarantee is exactly why std::map / TreeMap pick RB over AVL for update-heavy work.

Red uncle ::: recolour only (Case 1), push $z$ up, no rotation. Black uncle, zig-zag ::: rotate at parent $p$ to straighten (Case 2), then Case 3. Black uncle, straight line ::: recolour $p,g$, rotate at grandparent $g$, terminate (Case 3). New node's colour ::: always red. Max rotations per RB insert ::: 2.