Red-black trees are self-balancing binary search trees that guarantee O(lg n) worst-case time for all basic dynamic-set operations. By augmenting each node with a single color bit (red or black) and enforcing five structural properties, red-black trees ensure that no root-to-leaf path is more than twice as long as any other, keeping the tree approximately balanced. This chapter covers the red-black properties, rotations, and the intricate insertion and deletion fixup algorithms that maintain balance.
Every node is either red or black.
The root is black.
Every leaf (NIL) is black. (Leaves are sentinels, not key-bearing nodes.)
If a node is red, both its children are black. (No two consecutive red nodes on any path.)
For each node, all simple paths from that node to descendant leaves contain the same number of black nodes.
Sentinel T.nil: A single sentinel node (colored black) replaces all NIL pointers. Simplifies boundary-condition handling in the code. The root's parent is also T.nil.
Black-height (bh(x)): The number of black nodes on any simple path from node x down to a leaf, not counting x itself. Well-defined by property 5.
Lemma 13.1: A red-black tree with n internal nodes has height at most 2 lg(n + 1).
Proof sketch: The subtree rooted at any node x contains at least 2^(bh(x)) − 1 internal nodes (by induction). By property 4, at least half the nodes on any root-to-leaf path are black, so bh(root) ≥ h/2. Thus n ≥ 2^(h/2) − 1, giving h ≤ 2 lg(n + 1).
Immediate consequence: SEARCH, MINIMUM, MAXIMUM, SUCCESSOR, and PREDECESSOR all run in O(lg n) time, since they depend only on tree height.
Rotations: Local operations that restructure the tree while preserving the BST property. Two types:
LEFT-ROTATE(T, x): Makes x's right child y the new subtree root, with x becoming y's left child and y's former left subtree becoming x's right subtree.
RIGHT-ROTATE(T, y): The symmetric inverse.
Both run in O(1) time, changing only a constant number of pointers.