One extra bit per node and five invariants, which together force the height below 2 lg(n+1) on every input — so O(lg n) stops being a hope and becomes a guarantee.
Chapter 12 left a binary search tree that is excellent when balanced and useless when not, with no mechanism to tell the difference. A red-black tree is a BST that stores one bit of colour per node and maintains five properties which no sequence of insertions or deletions is allowed to break. Those properties bound the height at 2 lg(n+1), so every O(h) operation from Chapter 12 becomes O(lg n) in the worst case. Search, minimum, maximum, successor, predecessor, and the in-order walk are inherited unchanged. Only insertion and deletion need new machinery, and that machinery is this chapter.
T.nil sentinel is used throughout, and the insert and delete fixup cases are laid out more explicitly. This is also the chapter where reading the sentinel discussion from Chapter 10 pays off — the fixup code would be far uglier with NIL tests.Each node carries an extra attribute color, either RED or BLACK, alongside key, left, right, and p. A binary search tree is a red-black tree if it satisfies all five:
NIL) is black.Properties 4 and 5 are the working ones. Property 4 says red nodes cannot stack up; property 5 says black nodes are distributed perfectly evenly. Together they mean the longest root-to-leaf path can be at most twice the shortest: the shortest is all black, and the longest alternates red and black.
x, written bh(x), is the number of black nodes on any simple path from x down to a leaf, not counting x itself. Property 5 is exactly the statement that this is well defined — every downward path from x gives the same count.Property 3 requires every NIL to be a black leaf, and the algorithms constantly need to read x.p or x.color for nodes at the boundary. Rather than scatter NIL tests everywhere, CLRS uses the Chapter 10 trick: a single sentinel object T.nil.
T.nil.color = BLACK, satisfying property 3 for free.NIL child pointer and the root’s parent pointer point to T.nil instead.key, left, right, and p fields are unspecified — the algorithms may write to them freely as scratch and never read anything meaningful back.x.p when x may be T.nil, and that only works because the sentinel is a real object whose parent pointer the code has arranged. Trying to implement red-black deletion with genuine null pointers is where most from-scratch attempts fall apart.O(lg n)n internal nodes has height at most 2 lg(n + 1).The proof runs in two steps and is worth carrying because it shows exactly which property does which job.
Step 1: a subtree rooted at x contains at least 2bh(x) - 1 internal nodes. By induction on height. If x is a leaf, bh(x) = 0 and the subtree has 2⁰ - 1 = 0 internal nodes. Otherwise each child of x has black-height bh(x) or bh(x) - 1, depending on its own colour, so by the inductive hypothesis each child’s subtree has at least 2bh(x)-1 - 1 internal nodes. Adding the two children plus x:
(2bh(x)-1 - 1) + (2bh(x)-1 - 1) + 1 = 2bh(x) - 1Step 2: at least half the nodes on any root-to-leaf path are black. This is property 4 doing its work. Red nodes cannot be adjacent, so on a path of length h at most h/2 nodes are red, and therefore bh(root) ≥ h/2.
Combine them:
n ≥ 2bh(root) - 1 ≥ 2h/2 - 1
n + 1 ≥ 2h/2
lg(n + 1) ≥ h/2
h ≤ 2 lg(n + 1)The immediate payoff: every Chapter 12 query — SEARCH, MINIMUM, MAXIMUM, SUCCESSOR, PREDECESSOR — runs unmodified on a red-black tree and now costs O(lg n) in the worst case. They never inspect the colours at all.
Insertion and deletion break the properties, and fixing them requires changing the tree’s shape. The primitive for that is the rotation: a local restructuring that changes pointers among three nodes while preserving the binary-search-tree property.
β changes parent, everything else just re-links. Left and right rotations are exact inverses.LEFT-ROTATE(T, x)
1 y = x.right // set y
2 x.right = y.left // turn y's left subtree into x's right subtree
3 if y.left ≠ T.nil
4 y.left.p = x
5 y.p = x.p // link x's parent to y
6 if x.p == T.nil
7 T.root = y
8 elseif x == x.p.left
9 x.p.left = y
10 else x.p.right = y
11 y.left = x // put x on y's left
12 x.p = yO(1) — a fixed number of pointer writes, independent of subtree size. RIGHT-ROTATE is the mirror image, with left and right exchanged throughout.
Insert as an ordinary BST would, colour the new node red, then repair.
RB-INSERT(T, z)
1 x = T.root
2 y = T.nil
3 while x ≠ T.nil // descend to a leaf position
4 y = x
5 if z.key < x.key
6 x = x.left
7 else x = x.right
8 z.p = y
9 if y == T.nil
10 T.root = z
11 elseif z.key < y.key
12 y.left = z
13 else y.right = z
14 z.left = T.nil
15 z.right = T.nil
16 z.color = RED // always red — see below
17 RB-INSERT-FIXUP(T, z)Lines 1–13 are TREE-INSERT from Chapter 12 with NIL replaced by T.nil. Lines 14–17 are new.
So after insertion, exactly one property can be broken:
z is the root. Trivially fixed by recolouring the root black.z.p is red. This is the real work.The fixup loop pushes the violation up the tree until it can be resolved. The controlling question at each step is the colour of z’s uncle — the sibling of z’s parent.
RB-INSERT-FIXUP(T, z)
1 while z.p.color == RED
2 if z.p == z.p.p.left
3 y = z.p.p.right // y is z's uncle
4 if y.color == RED // ---- case 1
5 z.p.color = BLACK
6 y.color = BLACK
7 z.p.p.color = RED
8 z = z.p.p // move the violation up two levels
9 else
10 if z == z.p.right // ---- case 2
11 z = z.p
12 LEFT-ROTATE(T, z) // turn case 2 into case 3
13 z.p.color = BLACK // ---- case 3
14 z.p.p.color = RED
15 RIGHT-ROTATE(T, z.p.p) // and we are done
16 else (same as lines 3–15 with "right" and "left" exchanged)
17 T.root.color = BLACK| Case | Uncle | Shape | Action | Result |
|---|---|---|---|---|
| 1 | RED | either | Recolour only. Parent and uncle become black, grandparent becomes red. | Violation moves up two levels. Loop continues. |
| 2 | BLACK | z is a right child (a “zig-zag”) |
Left-rotate on z.p to straighten the line. |
Becomes case 3. |
| 3 | BLACK | z is a left child (a straight line) |
Recolour parent black and grandparent red, then right-rotate on the grandparent. | Done. Loop exits. |
O(lg n). Only case 1 continues the loop, and it moves z two levels up each time. So there are at most h/2 = O(lg n) iterations. Cases 2 and 3 each perform a rotation and then exit. Consequently RB-INSERT performs at most two rotations in total, no matter how large the tree.The loop invariant CLRS maintains is worth noting: at the start of each iteration, z is red, and if z.p is the root then z.p is black, and at most one property is violated — either 2 or 4, never both. Line 17 unconditionally blackens the root, which fixes property 2 if case 1 reddened the root on its last pass.
Deletion is the harder half, for a structural reason: removing a black node reduces the black-height of every path through it, breaking property 5, and property 5 is global.
The chapter needs a modified transplant that uses the sentinel and, crucially, sets v.p unconditionally:
RB-TRANSPLANT(T, u, v)
1 if u.p == T.nil
2 T.root = v
3 elseif u == u.p.left
4 u.p.left = v
5 else u.p.right = v
6 v.p = u.p // no NIL test — this is why we need T.nilCompare with TRANSPLANT in Chapter 12, which guarded line 6 with if v ≠ NIL. Here v may be T.nil and we assign its parent anyway, deliberately, because the fixup needs to climb from it.
RB-DELETE(T, z)
1 y = z
2 y-original-color = y.color
3 if z.left == T.nil
4 x = z.right
5 RB-TRANSPLANT(T, z, z.right)
6 elseif z.right == T.nil
7 x = z.left
8 RB-TRANSPLANT(T, z, z.left)
9 else
10 y = TREE-MINIMUM(z.right) // the successor
11 y-original-color = y.color
12 x = y.right
13 if y.p == z
14 x.p = y
15 else
16 RB-TRANSPLANT(T, y, y.right)
17 y.right = z.right
18 y.right.p = y
19 RB-TRANSPLANT(T, z, y)
20 y.left = z.left
21 y.left.p = y
22 y.color = z.color // y inherits z's colour
23 if y-original-color == BLACK
24 RB-DELETE-FIXUP(T, x) // only then is anything brokenRB-DELETE. First, y is the node actually removed from its position — either z itself, or z’s successor when z has two children. Second, line 22 gives y the colour of z, so the tree’s colouring at that position is unchanged; what matters is the colour y had at its old position, saved in y-original-color. Third, if that colour was red, nothing is broken and no fixup runs — removing a red node cannot change any black-height or create two adjacent reds.When a black node is removed, the fix is conceptual: pretend the node x that moved into its place carries an extra black. That restores property 5 arithmetically but makes x “doubly black”, which is not a real colour. The fixup’s job is to push that extra black up the tree until it can be discarded.
The controlling node is w, the sibling of x. Assuming x is a left child (the right-child cases mirror exactly):
| Case | Condition on sibling w | Action | Result |
|---|---|---|---|
| 1 | w is red |
Recolour w black and x.p red, then left-rotate on x.p. |
New sibling is black. Converts to case 2, 3, or 4. |
| 2 | w black, both of w’s children black |
Recolour w red, move x up to x.p. |
Extra black moves up one level. Loop continues. |
| 3 | w black, w.left red, w.right black |
Recolour w.left black and w red, right-rotate on w. |
Becomes case 4. |
| 4 | w black, w.right red |
Copy x.p’s colour to w, blacken x.p and w.right, left-rotate on x.p, set x = T.root. |
Done. Loop exits. |
RB-DELETE-FIXUP(T, x)
1 while x ≠ T.root and x.color == BLACK
2 if x == x.p.left
3 w = x.p.right // sibling
4 if w.color == RED // case 1
5 w.color = BLACK
6 x.p.color = RED
7 LEFT-ROTATE(T, x.p)
8 w = x.p.right
9 if w.left.color == BLACK and w.right.color == BLACK
10 w.color = RED // case 2
11 x = x.p
12 else
13 if w.right.color == BLACK // case 3
14 w.left.color = BLACK
15 w.color = RED
16 RIGHT-ROTATE(T, w)
17 w = x.p.right
18 w.color = x.p.color // case 4
19 x.p.color = BLACK
20 w.right.color = BLACK
21 LEFT-ROTATE(T, x.p)
22 x = T.root // terminate
23 else (same with "right" and "left" exchanged)
24 x.color = BLACKx up one level, so there are at most O(lg n) iterations. Cases 1, 3, and 4 each do at most one rotation and either transform into another case or terminate. Total: at most three rotations for a deletion, and O(lg n) time.Line 24 is the discharge. If the loop exits because x is red, colouring it black absorbs the extra black and restores everything. If it exits because x is the root, the extra black simply disappears — removing one black from every path preserves property 5.
RB-DELETE-FIXUP from memory, and there is no reason to. What is worth carrying is the structure: an extra black is pushed up the tree, the sibling’s colour and its children’s colours select the case, only one case loops, and the whole thing is O(lg n) with at most three rotations. If you need the code, look it up — or, far better, use the balanced tree your standard library already ships.| Operation | Red-black tree | Plain BST | Hash table |
|---|---|---|---|
SEARCH | O(lg n) worst | O(n) worst | O(1) expected |
INSERT | O(lg n) worst | O(n) worst | O(1) expected |
DELETE | O(lg n) worst | O(n) worst | O(1) expected |
MINIMUM / MAXIMUM | O(lg n) | O(n) worst | Impossible |
SUCCESSOR / PREDECESSOR | O(lg n) | O(n) worst | Impossible |
| Sorted traversal | Θ(n) | Θ(n) | Requires a sort |
| Range query | O(lg n + k) | O(n) worst | Impossible |
| Rotations per update | ≤ 2 insert, ≤ 3 delete | 0 | — |
O(n) rehash. Otherwise the hash table wins on constant factors, and by a lot.std::map and std::set, Java TreeMap and TreeSet, and the Linux kernel’s scheduler, memory manager, and epoll implementation are all red-black trees. The alternatives are AVL trees (more rigidly balanced, so faster lookups and more rotations per update) and B-trees from Chapter 18 (better when nodes live on disk). Red-black trees sit at a sweet spot of update cost versus balance quality, which is why they are the default.T.nil) is black; a red node has black children; and every path from a node to its descendant leaves has the same number of black nodes.bh(x) counts black nodes below x, excluding x. Property 5 is what makes it well defined.h ≤ 2 lg(n+1). Property 5 makes the tree bushy; property 4 caps the stretch at a factor of 2.T.nil sentinel is one shared object serving as every leaf and the root’s parent. Deletion’s fixup depends on being able to write and read its parent pointer.O(1), change only pointers, and preserve the in-order sequence, so the BST property always survives.O(lg n) worst case. Use a balanced tree over a hash table when you need ordering or a guarantee.Part III is complete: hash tables for unordered speed, balanced trees for ordered guarantees. Part IV changes register entirely, from structures to design techniques. Chapter 14 covers dynamic programming, which solves optimisation problems by identifying overlapping subproblems and solving each exactly once. The red-black tree returns in Chapter 17, where augmenting it with extra fields per node yields order-statistic trees and interval trees at no asymptotic cost.