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

False — AVL is tighter (subtree heights differ by at most 1); RB only promises the longest path is at most twice the shortest, so an RB tree can be taller than the AVL tree for the same data.

True — the coloring rules are layered on top of BST ordering; every operation (including rotations) preserves the left-<-node-<-right invariant, so RB is a BST first and colored second.

True temporarily — Case 1 recoloring can paint the grandparent (which may be the root) red, but the fixup loop's final line forces the root back to black, so the finished tree always has a black root.

False — "no red-red" is only property 4; you still need the equal-black-height property 5, the black root, and black NIL leaves. A tree can be red-red-free yet have unequal black-heights.

False in general — an all-black coloring satisfies property 4 (no red-red) but property 5 fails whenever the tree's shape is unbalanced, since then two root-to-NIL paths of different length have different black counts. It is valid only when the underlying shape already has every root-to-NIL path the same length (a perfectly balanced tree).

False — insertion order and the specific fixup cases taken can produce different (all valid) colorings and shapes; RB trees are not canonical for a key set.

True — both paths have black-height 3, satisfying property 5; the reds don't count toward black-height, so extra reds on one path are allowed as long as no two touch.

False (by this page's convention, stated in the notation box) — $bh(x)$ counts the black nodes on paths below $x$ down to NIL, excluding $x$; the NIL leaves themselves are the black endpoints that get counted.

Error: new nodes are inserted red. A black insert adds one to the black-height of a single path, instantly breaking property 5 — the hardest property to repair. Red can only break the easy property 4.

Error: rotation is only for a black (or NIL) uncle $u$. If $u$ is red, plain recoloring (Case 1) fixes it and pushes the problem upward — rotating there would be wasted, over-corrective work.

Error: the grandparent $g$ must be flipped to red. Making both children black without reddening $g$ adds a black to every path through it, breaking equal black-heights; reddening $g$ keeps the counts balanced.

Error: $g$ just turned red and may now clash with its parent, so you must set the cursor $z=g$ and re-check upward. The problem floats up, it doesn't vanish.

Error: that's the grandparent $g$. The uncle $u$ is the parent $p$'s sibling — $g$'s other child.

Error: NIL sentinels are real black leaves and are exactly the endpoints property 5 counts paths to. Ignoring them breaks the whole black-height accounting.

Error: the inner case (Case 2) rotates at the parent $p$ first, to straighten the $g$–$p$–$z$ line into the outer case (Case 3); only then does Case 3 rotate at the grandparent $g$.

Error: rotation is order-preserving. Before and after, $a<x<b<y<c$ holds; only the parent-child pointers change, never the in-order sequence.

Because red can only violate the cheap property 4 (red-red), fixable locally by recolor/rotate, whereas black would violate property 5 (equal black-heights) on just one path — a global, expensive-to-repair break.

Property 5 forces equal black nodes on every path, and property 4 forbids two reds in a row, so at most half a path's nodes are red; the reddest path is thus at most double the all-black path.

RB accepts a looser balance (2× spread), so many violations are fixed by cheap recoloring alone; a single insert needs at most a constant number of rotations, while AVL's strict height-1 rule triggers rotations more often. See AVL Tree and Tree Rotations.

Update-heavy workloads benefit from RB's fewer rotations per insert/delete; the slightly larger height barely affects lookup, and the constant rotation bound gives predictable performance. See std::map / TreeMap internals.

Turning the root black adds exactly one black node to every root-to-NIL path equally, so all black-heights rise together — property 5 stays satisfied and no red-red is introduced.

We add one black on both of $g$'s sides ($p$ and $u$ both go black) and remove one from $g$ (it goes red), so every path through $g$ keeps its original black count.

Case 3 lifts a black node to the local subtree root, restoring both children's black-heights and killing the red-red in one shot with nothing pushed up; Case 1 only relocates the problem to $g$, which may still conflict with its parent.

It rearranges a fixed, small number of pointers (a constant handful) regardless of tree size — no traversal or per-node work scales with $n$. See Big-O Analysis.

Each black node with its attached red children maps to a single 2-3-4 node (a 2-, 3-, or 4-node), so RB is a binary encoding of a perfectly-balanced 2-3-4 tree — which is why every RB path has equal black-height. See 2-3-4 Tree.

Yes — that node is the root and must be black (property 2). Its two children are black NIL sentinels, giving a valid black-height of 1.

Yes — the empty tree is just the NIL sentinel, which is black by property 3; there are no nodes to violate any rule.

Nothing to fix — a red $z$ under a black $p$ creates no red-red, black-heights are untouched, so the fixup loop never even starts.

Black — NIL is always a black leaf, so a missing uncle triggers the black-uncle branch (Case 2/3, rotate-and-recolor), not the recolor-only Case 1.

Only if the real child is red; the NIL child is black and can never cause red-red. A red node with a black NIL on one side and a red data child on the other still violates property 4.

Yes — repeated Case 1 recoloring can propagate up to the root; the loop then stops because the root has no parent, and the final step recolors the root black.

Yes — deletion is trickier than insertion because removing a black node reduces one path's black count; the fix models the missing black as a temporary "double-black" that is pushed up or resolved via sibling recoloring/rotation until property 5 is restored.

About $h/2$ — since at most half the nodes on any path are red (property 4), the black nodes number at least $h/2$, which is exactly the fact used to derive $h\le 2{\log }_2(n+1)$.