Red-Black Trees: Invariants, Rotations, and O(log n) Guarantees
What This Concept Is
A red-black tree combines BST ordering with colors: the root and absent-child NIL sentinels are black; a red node has black children; and all paths from a node to a NIL have equal black counts. These invariants bound path lengths, but rotations and recoloring must preserve all of them after updates.
Use one insertion/deletion variant consistently. Classic red-black fixups and left-leaning variants have different case rules and rotation analyses. The core lab implements a complete AVL map; this lesson requires red-black reasoning and traces, with a red-black implementation as a depth option.
Why It Matters Here
Color rules provide a worst-case search-height guarantee independent of insertion order. Learning the proof separates a balance invariant from a claim that a particular standard-library implementation uses it.
Concrete Examples
Let b count black internal nodes on a root-to-NIL path, including the black
root and excluding NIL. A tree with black count b has at least 2^b-1
internal nodes: recursively, each black layer requires both child subtrees to
support the remaining black count. Red nodes cannot be adjacent, so any path
contains at most 2b internal nodes. Consequently height measured in edges to
NIL is at most 2 log2(n+1). Declare conventions to avoid an off-by-one dispute.
Insertion 10,5,1. Insert each new node red, making the root black. After 1 is inserted below red 5, parent and child are both red. The uncle is black NIL and the shape is left-left. Rotate right at 10 and recolor: root 5 black, children 1 and 10 red. Ordering and all black path counts agree. A red uncle instead leads first to recoloring and possibly a violation higher up.
Deletion reasoning. Removing a red leaf does not change black counts. Removing a black node can create a one-black deficit on one branch. Repair cases depend on sibling and nephew colors; ordinary BST deletion alone cannot preserve the color invariants. Classic algorithms use a bounded number of rotations but may propagate recoloring/deficit work along O(log n) ancestors.
Common Confusion / Misconceptions
The height bound applies to search and bounded-path updates, not to outputting all n items in O(log n). Constant rotation counts depend on the specified classic algorithm; do not transfer them to every left-leaning implementation. Do not claim Java TreeMap uses Sedgewick's left-leaning algorithm or infer standard-library internals from interface guarantees.
How To Use It
Draw the local key ordering before rotating and verify colors/black counts afterward. For each trace, include NIL paths and both red-uncle and black-uncle cases. If implementing the depth option, independently validate ordering, black height, red adjacency and node ownership after mixed insert/delete sequences.
Check Yourself
Why does equal black height alone not prevent arbitrarily long all-red chains? What makes deletion different from insertion? Which guarantees survive changing implementation variants?
Mini Drill or Application
Insert 10,5,15,1 using a classic red-black insertion algorithm. Feedback: red parent 5 and red uncle 15 are recolored black; 10 is temporarily red then restored black as root. Check all NIL paths.
Read This Only If Stuck
CLRS: red-black invariants, insertion and deletion. Work through one named variant end to end; compare implementations only after the proof is clear.