Red-Black Trees
the balanced BST powering Linux, Java, and C++ — how the five invariants make O(log n) a hard guarantee.
- DATE:
- APR.30.2026
- READ:
- 26 MIN
You’ve been using red-black trees your entire career. Every call to std::map in C++, every Java TreeMap, every insert on the Linux CFS scheduler run queue — all backed by the same structure. Yet most explanations stop at “it’s self-balancing, trust it.” Let’s not stop there.
Where it came from
The story starts in 1972 with Rudolf Bayer’s paper Symmetric binary B-Trees: Data structure and maintenance algorithms. Bayer was generalizing B-trees — the disk-friendly multi-key structures used in databases — for in-memory use. His structure encoded a 2–3–4 tree (B-tree of order 4) as a collection of binary nodes connected by two kinds of links: vertical links between B-tree levels, and horizontal links between keys within the same B-tree node. He called the horizontal ones “symmetric” because they could lean either left or right.
The color didn’t arrive until 1978. Leonidas Guibas and Robert Sedgewick published A Dichromatic Framework for Balanced Trees at the IEEE Symposium on Foundations of Computer Science. They took Bayer’s structure, assigned a color bit to each link (or equivalently, to each node), and gave the two-color scheme its name. Why red? Sedgewick explains it directly: they were at Xerox PARC, and red was the best-looking color their color laser printer produced.
Robert Tarjan contributed two refinements in the mid-1980s: a proof that insertion requires only O(1) amortized rotations (even though recolorings can cascade O(log n) levels), and the amortized analysis technique itself, introduced in his 1985 SIAM paper. This was important — it explained why red-black trees are faster in practice than the worst-case rotation count suggests.
The modern textbook formulation — six fix-up cases, the double-black deletion machinery, the left-rotate / right-rotate pseudocode — crystallised in Cormen, Leiserson, Rivest, and Stein’s Introduction to Algorithms (first edition 1990, Chapter 13 in all subsequent editions). That is the version everyone implements.
The five invariants
A red-black tree is a binary search tree where every node carries one extra bit: its color. The structure guarantees O(log n) operations by maintaining five properties simultaneously:
- Every node is red or black.
- The root is black.
- No two consecutive red nodes. A red node cannot have a red parent (equivalently: cannot have a red child). This is the “no red-red” rule.
- Uniform black-height. Every path from any node down to any null leaf passes through the same number of black nodes. This count is the node’s black-height, written bh(x).
- Null leaves are black. The NIL sentinels at the bottom of the tree are considered black. This is bookkeeping — it lets the other rules apply cleanly at boundaries.
Properties 3 and 4 together are what buys you the height guarantee. Property 4 ensures the tree is “B-tree balanced” — all paths have equal black depth, mirroring the all-leaves-at-the-same-level invariant of a B-tree. Property 3 prevents red nodes from stacking, so no path can be more than twice the length of another.
The tree above holds all five properties after inserting [7, 3, 18, 10, 22, 8, 11, 26]. Every path from root to a NIL leaf crosses exactly 2 black nodes. Node 18 is red (it’s an “intra-cluster” connection in B-tree terms), but its parent 7 is black and its children 10 and 22 are both black — no consecutive reds anywhere.
The height bound
The reason this matters: with these five properties, you can prove the tree height is at most 2·log₂(n+1).
Lemma 1 — subtree size: Any node x with black-height bh(x) has a subtree of at least 2^bh(x) − 1 internal nodes.
Proof by induction. Base: a NIL leaf has bh = 0 and contains 2⁰ − 1 = 0 nodes. Inductive step: a node x with black-height b has two children each with black-height ≥ b − 1 (a black child decrements the count, a red child doesn’t). By the inductive hypothesis, each subtree has at least 2^(b−1) − 1 nodes. So x’s subtree has at least 1 + 2·(2^(b−1) − 1) = 2^b − 1 nodes. ∎
Lemma 2 — black-height vs. height: Property 3 forbids consecutive reds, so at least half the nodes on any root-to-leaf path are black. Therefore bh(root) ≥ h/2, i.e., h ≤ 2·bh(root).
Combining: From Lemma 1: n ≥ 2^bh(root) − 1, so bh(root) ≤ log₂(n+1). From Lemma 2: h ≤ 2·bh(root). Therefore:
h ≤ 2·log₂(n+1)A red-black tree with 1 billion nodes has height at most 2·log₂(10⁹+1) ≈ 60. Every lookup, insert, or delete touches at most 60 nodes. That’s the hard guarantee.
The 2-3-4 tree in disguise
You cannot fully understand red-black trees without understanding what they’re encoding. A 2-3-4 tree is a B-tree of order 4: nodes can hold 1, 2, or 3 keys, with 2, 3, or 4 children respectively. All leaves sit at the same depth — it’s perfectly balanced.
A red-black tree is a binary encoding of a 2-3-4 tree. The translation:
| 2-3-4 node | Red-black encoding |
|---|---|
| 2-node (1 key) | single black node |
| 3-node (2 keys) | black node + one red child |
| 4-node (3 keys) | black node + two red children |
Red links are horizontal — they connect keys within the same B-tree node. Black links are vertical — they connect B-tree levels. This is exactly why Property 4 (uniform black-height) holds: all paths in a 2-3-4 tree traverse the same number of node levels, which corresponds to the same number of black links.
And why does Property 3 (no red-red) hold? Within any 2-3-4 node you have at most 3 keys, encoding as 1 black + 2 red children. Those red children connect to keys in the next B-tree level, which are the roots of sub-2-3-4 nodes — and sub-2-3-4 node roots are black.
Every red-black tree operation maps to a 2-3-4 tree operation:
- Case 1 fix-up during insertion (uncle is red → recolor) = splitting a 4-node in the 2-3-4 tree
- Case 2 + 3 fix-up (rotations) = absorbing into a 2-node or 3-node to form a 3-node or 4-node
Once you see this, the five invariants stop being rules to memorize and become consequences of the underlying structure.
Rotations
Rotations are the atomic operation that maintains tree shape during rebalancing. They rearrange a local 3-node cluster in O(1) time while preserving the BST ordering property.
In a left rotation on node x (where x has right child y):
yascends tox’s positionxdescends toy’s left childy’s old left subtreeβreattaches asx’s new right subtree
The BST property is preserved because before the rotation: α < x < β < y < γ. After: α < x (x’s left unchanged), β > x (reattached as x’s right), x < y (x is now y’s left child), γ > y (y’s right unchanged). The ordering is identical.
Six pointer updates total. Right rotation is the exact mirror.
def left_rotate(T, x):
y = x.right # y is x's right child
x.right = y.left # y's left subtree becomes x's right
if y.left is not T.nil:
y.left.parent = x # update parent of moved subtree
y.parent = x.parent # y takes x's place
if x.parent is T.nil:
T.root = y # x was root
elif x is x.parent.left:
x.parent.left = y # x was a left child
else:
x.parent.right = y # x was a right child
y.left = x # x descends to y's left
x.parent = yInsertion
The algorithm
- Do a standard BST insert — find the position, create the node, color it red.
- Check if the parent is red. If so, we have a Property 3 violation. Fix it.
Why insert as red? Inserting as black would immediately break Property 4 by adding one black node to some paths but not others. Inserting as red only risks Property 3 — and only if the parent is red. That’s the easier violation to fix.
The three fix-up cases
Let z be the new node, p its parent (red), g its grandparent (necessarily black — if p is red, p’s parent must be black or we’d have had a violation before this insertion). Let u be the uncle (g’s other child).
Case 1: Uncle is red.
This corresponds to a 4-node in the 2-3-4 tree — a split. Recolor p and u to black, g to red. Move the problem up to g (it might now conflict with its parent). Continue the loop from g.
No rotations. Only recolorings. Can cascade O(log n) levels toward the root.
Case 2: Uncle is black, and z is an inner grandchild (triangle shape).
p is g’s left child and z is p’s right child (or the symmetric Right-Left case). The nodes form a zig-zag. Rotate at p to straighten the zig-zag into a line. This doesn’t fix the violation — it transforms Case 2 into Case 3.
Case 3: Uncle is black, and z is an outer grandchild (line shape).
p is g’s left child and z is p’s left child (or the symmetric Right-Right case). Rotate at g, then swap colors of p and g. The violation is resolved. The loop terminates.
Total: at most 2 rotations per insertion (Case 2 + Case 3 back-to-back). The loop runs at most O(log n) times but only Case 1 recurses upward; Cases 2 and 3 terminate immediately.
Step-by-step: inserting [7, 3, 18, 10, 22, 8, 11, 26]
Starting with an empty tree:
7 → root, color black (Property 2).
3 → left of 7, colored red. Parent 7 is black → no violation.
18 → right of 7, colored red. Parent 7 is black → no violation.
Tree: 7(B) left=3(R) right=18(R)
10 → right of 7, left of 18. Color red. Parent 18(R) — violation. Uncle = 3(R) → Case 1: recolor 18→B, 3→B, 7→R. But 7 is root → recolor back to black.
Tree: 7(B), 3(B), 18(B), 18.left=10(R)
22 → right of 18. Color red. Parent 18(B) → no violation.
8 → right of 7, left of 18, left of 10. Color red. Parent 10(R) — violation. Uncle = 22(R) → Case 1: recolor 10→B, 22→B, 18→R. Parent of 18 is 7(B) → no new violation.
Tree: 7(B), 3(B), 18(R); 18 has 10(B) [left=8(R)] and 22(B)
11 → right of 10. Color red. Parent 10(B) → no violation.
26 → right of 22. Color red. Parent 22(B) → no violation.
Final tree (all five properties satisfied, bh = 2):
7 (B)
/
3 (B) 18 (R)
/
10 (B) 22 (B)
/
8 (R) 11 (R) 26 (R)Deletion
Deletion is significantly harder. The short version: when you delete a black node and replace it with a black child (or NIL), one path loses a black node. We label the replacement “double-black” — a conceptual marker meaning “this node owes one black to all paths below it.” Then we propagate and resolve this debt.
The six sibling sub-cases
Let db be the double-black node and s its sibling:
| Case | Sibling s | Sibling’s children | Action |
|---|---|---|---|
| 1 | RED | (both black by P3) | Rotate toward db at db’s parent; swap colors. Converts to 2–4. |
| 2 | BLACK | both BLACK, parent also BLACK | Recolor s RED. Push double-black up to parent. |
| 3 | BLACK | both BLACK, parent RED | Swap s and parent colors. Done — no cascading. |
| 4 | BLACK | near nephew RED, far nephew BLACK | Rotate at s toward far side; swap colors. Converts to case 5. |
| 5 | BLACK | far nephew RED | Rotate at parent toward db; swap parent/sibling colors; color far nephew black. Done. |
Case 1 doesn’t fix double-black but converts the structure to cases 2–5 with a guaranteed black sibling. Cases 2 and 3 are the “fix by recoloring” cases — case 3 always terminates, case 2 can cascade. Cases 4 and 5 always terminate with at most 3 rotations total.
In practice, deletion terminates in O(1) rotations amortized (Tarjan, 1985).
Red-black vs. AVL
AVL trees (Adelson-Velsky and Landis, 1962) use a stricter balance condition: the heights of any node’s two subtrees must differ by at most 1. This gives a tighter height bound of ≤ 1.44·log₂(n+1) vs. red-black’s 2·log₂(n+1).
+--------------------+--------------------+--------------------+ | Dimension | AVL | Red-Black | +--------------------+--------------------+--------------------+ | Balance condition | height diff ≤ 1 | no red-red + | | | | uniform bh | +--------------------+--------------------+--------------------+ | Height bound | ≤ 1.44 log₂(n+1) | ≤ 2 log₂(n+1) | +--------------------+--------------------+--------------------+ | Lookup | faster (shorter | slightly slower | | | tree) | | +--------------------+--------------------+--------------------+ | Insert rotations | up to O(log n) | at most 2 | +--------------------+--------------------+--------------------+ | Delete rotations | up to O(log n) | at most 3 | +--------------------+--------------------+--------------------+ | Write-heavy perf | slower | faster | +--------------------+--------------------+--------------------+ | Color/balance | balance factor: 2 | color: 1 bit | | storage | bits | | +--------------------+--------------------+--------------------+ | Typical use | read-heavy DB | OS kernels, stdlib | | | indexes | maps | +--------------------+--------------------+--------------------+
The trade-off is clean: AVL is ~28% shorter in the worst case, buying faster lookups. But every insert or delete may trigger O(log n) rotations to restore the strict height invariant. Red-black trees require O(1) amortized rotations — far cheaper for write-heavy or mixed workloads. That’s why every major programming language’s standard library chose red-black over AVL.
A 2024 empirical study (arXiv:2406.05162) found that AVL deletion is actually faster than RB deletion in practice for certain access patterns — the conventional wisdom about RB being universally faster on writes is slightly overstated. The difference is small enough that RB’s implementation simplicity and amortized guarantees keep it dominant.
Where it runs today
Linux CFS scheduler (kernel/sched/fair.c)
The Completely Fair Scheduler, merged in Linux 2.6.23 (2007), models fairness via virtual runtime: a weighted measure of how much CPU time each runnable task has consumed. The per-CPU run queue is an RB tree keyed on p->se.vruntime. The scheduler always picks the leftmost node — the most CPU-deprived task. That leftmost pointer is cached in cfs_rq->rb_leftmost for O(1) access; only insertions and deletions need O(log n).
The kernel also uses rbtree (in lib/rbtree.c) for:
- High-resolution timer management (timers sorted by expiry time)
- Virtual memory area (VMA) management within each process
- epoll interest list — each file descriptor registered via
epoll_ctl(EPOLL_CTL_ADD)is inserted into an RB tree keyed on the fd number, makingepoll_ctlO(log n) (and lookup before ADD is also O(log n)) - Deadline and CFQ I/O schedulers
- ext4 directory entries
Java TreeMap and TreeSet
java.util.TreeMap has been RB-backed since Java 1.2. The Javadoc says: “This implementation provides guaranteed log(n) time cost for containsKey, get, put and remove.” TreeSet is a thin wrapper around TreeMap with a dummy value.
Java 8 added a twist: HashMap and HashSet convert collision chains longer than 8 elements from linked lists to RB trees (the TreeNode inner class in java.util.HashMap). This protects against hash-flooding attacks and degenerate inputs by capping worst-case bucket lookup at O(log m) instead of O(m).
C++ std::map, std::set, std::multimap, std::multiset
The C++ standard doesn’t mandate RB trees but requires O(log n) amortized complexity for insert, erase, and find. Every major implementation — GCC’s libstdc++ (_Rb_tree in <bits/stl_tree.h>), LLVM’s libc++, MSVC’s STL — uses RB trees. The template machinery is complex but the underlying tree structure is identical to CLRS Chapter 13.
Nginx timer management
Nginx keeps all active timeouts (connection timeouts, proxy timeouts, keepalive) in a global RB tree ngx_event_timer_rbtree keyed by expiry time in milliseconds. The event loop reads the leftmost node as the timeout argument for epoll_wait(). When events fire, ngx_event_expire_timers() pops leftmost nodes until it hits a non-expired entry. This is the canonical “min-heap via RB tree” pattern — it supports O(log n) deletion of arbitrary timers, which binary heaps can’t do efficiently.
Left-leaning red-black trees
Sedgewick revisited the structure in 2008 with a restriction: red links must always lean left. A 3-node’s red child can only be a left child. This creates a 1-to-1 correspondence with 2–3 trees (not 2–3–4 trees) and collapses the insert algorithm to three helper functions: rotateLeft, rotateRight, flipColors.
def insert(self, h, key):
if h is None:
return Node(key, RED)
if key < h.key:
h.left = self.insert(h.left, key)
elif key > h.key:
h.right = self.insert(h.right, key)
# Fix-up: three cases
if is_red(h.right) and not is_red(h.left):
h = rotate_left(h) # no right-leaning reds
if is_red(h.left) and is_red(h.left.left):
h = rotate_right(h) # no two consecutive left reds
if is_red(h.left) and is_red(h.right):
flip_colors(h) # split 4-node
return hElegant — but Eddie Kohler’s 2011 critique Left-Leaning Red-Black Trees Considered Harmful measured that LLRB deletion requires 51.99× more rotations than standard RB deletion due to proactive restructuring. LLRB is pedagogically valuable (the insert is genuinely readable) but standard RB remains the production choice.
Implementing your own
Most production code never needs a custom RB tree — the standard library implementations are correct and fast. But the exercise of implementing one is worthwhile:
class Node:
def __init__(self, key):
self.key = key
self.color = RED
self.left = self.right = self.parent = NIL
class RBTree:
def __init__(self):
self.nil = Node(None)
self.nil.color = BLACK
self.root = self.nil
def insert(self, key):
z = Node(key)
z.left = z.right = z.parent = self.nil
# Standard BST insert
y = self.nil
x = self.root
while x is not self.nil:
y = x
x = x.left if z.key < x.key else x.right
z.parent = y
if y is self.nil:
self.root = z
elif z.key < y.key:
y.left = z
else:
y.right = z
# Fix-up
self._insert_fixup(z)
def _insert_fixup(self, z):
while z.parent.color == RED:
if z.parent is z.parent.parent.left:
y = z.parent.parent.right # uncle
if y.color == RED: # Case 1
z.parent.color = BLACK
y.color = BLACK
z.parent.parent.color = RED
z = z.parent.parent
else:
if z is z.parent.right: # Case 2 → Case 3
z = z.parent
self._left_rotate(z)
z.parent.color = BLACK # Case 3
z.parent.parent.color = RED
self._right_rotate(z.parent.parent)
else:
# Symmetric: uncle on the left side
y = z.parent.parent.left
if y.color == RED:
z.parent.color = BLACK
y.color = BLACK
z.parent.parent.color = RED
z = z.parent.parent
else:
if z is z.parent.left:
z = z.parent
self._right_rotate(z)
z.parent.color = BLACK
z.parent.parent.color = RED
self._left_rotate(z.parent.parent)
self.root.color = BLACKThis is the direct CLRS translation. The full deletion implementation adds 70 more lines for the double-black cases — see the resources below.
Numbers that matter
| n | max height | operations |
|---|---|---|
| 1,000 | ≤ 20 | trivial |
| 1,000,000 | ≤ 40 | trivial |
| 1,000,000,000 | ≤ 60 | still trivial |
| 10^18 | ≤ 120 | still trivial |
The 2·log₂(n+1) bound is so tight that red-black trees don’t break a sweat at scales that would kill O(n) or O(n²) structures. At 1 million tasks in the Linux CFS run queue, the scheduler still picks the next task in at most 40 comparisons.
Resources
Cormen, Leiserson, Rivest, Stein — Introduction to Algorithms, Chapter 13 (4th edition, MIT Press, 2022). The canonical academic reference for pseudocode and correctness proofs.
Guibas & Sedgewick — A Dichromatic Framework for Balanced Trees (1978). The original paper naming “red-black.” https://sedgewick.io/wp-content/themes/sedgewick/papers/1978Dichromatic.pdf
Sedgewick — Left-Leaning Red-Black Trees (2008). The elegant LLRB variant. https://sedgewick.io/wp-content/themes/sedgewick/papers/2008LLRB.pdf
Eddie Kohler — Left-Leaning Red-Black Trees Considered Harmful (2011). Why LLRB is slow on deletion. https://read.seas.harvard.edu/~kohler/notes/llrb.html
Linux kernel — Red-Black Trees (rbtree) documentation. https://docs.kernel.org/core-api/rbtree.html
Linux kernel — CFS Scheduler design. https://docs.kernel.org/scheduler/sched-design-CFS.html
arXiv:2406.05162 — Comparative Performance of the AVL Tree and Three Variants of the Red-Black Tree (2024). Empirical benchmark data. https://arxiv.org/abs/2406.05162