Red-Black Tree Simulator: colour-coded balance.

A red-black tree is a self-balancing binary search tree. Each node carries one extra bit indicating its colour (red or black), and five invariants on colour placement keep the tree height bounded at 2 log₂(n + 1). All standard operations (search, insert, delete) run in O(log n) worst case. The structure is used by the Linux kernel's CFS scheduler, every mainstream C++ std::map and std::set implementation, Java's TreeMap and TreeSet, and the kernel's EXT4 directory cache. It is the default in-memory balanced BST for almost every systems language.

Why not just use a plain BST? Because a plain BST has no balance guarantee. Insert 1, 2, 3, 4, 5 in order and you get a stick — a five-deep linked list where lookups cost O(n). The pathological case is the common case: real-world keys arrive in time order, ID order, alphabetical order, and a naive BST degenerates the moment the input has any structure. A self-balancing tree fixes this by rearranging itself on every mutation; the question is how much work each mutation does.

Red-black trees solve the balance problem with one bit of colour and a small set of rebalance cases. After every insert or delete, a fixup procedure walks up from the modified node, looking at the local colour pattern and either recolouring nodes (constant work) or performing one or two rotations (also constant work) before either terminating or propagating one level higher. The whole fixup is O(log n) in the worst case but O(1) amortised: most operations end after one or two recolours without ever rotating.

The simulator above lets you watch this happen. Insert keys one by one and watch the colours flip; insert a sequence like 10, 20, 30, 40, 50 and watch the tree refuse to become a stick — instead it rotates left at 20 to centre the tree, then again at 40. Every NIL leaf is shown as a small black square; this matters because the invariants are stated in terms of paths to NIL, not paths to leaf-nodes-with-keys. The convention is universal across textbook implementations.

The cost model worth carrying: an insert costs one BST descent (O(log n)) plus a fixup that is amortised O(1), with worst-case O(log n). A delete is similar but with more cases. A lookup is a plain BST descent, O(log n). Cache behaviour is decent — nodes are usually pointer-chasing structures, not page-aligned, so this is an in-memory data structure rather than a disk one. For disk, use a B-tree.

The five red-black invariants are the entire specification of the structure. Everything else (rotations, recolouring, the five insert cases, the six delete cases) is implementation detail that exists only to preserve them. Memorise them once and the rest follows.

1. Every node is either red or black. One bit of colour per node. Some implementations steal the low bit of the parent pointer; the Linux kernel does this in lib/rbtree.c to save 8 bytes per node.
2. The root is black. Always. If a fixup leaves it red, the last step is to recolour the root.
3. Every NIL leaf is black. The NIL leaves (often a shared sentinel object) are conceptually present at every position where a real subtree could attach. They have no keys; they exist only to make the invariants total.
4. A red node has only black children. No two reds in a row along any root-to-leaf path. This is the invariant that bounds height: between any two reds on a path, at least one black sits.
5. Every root-to-NIL path has the same number of black nodes. Call this the black height of the tree. It is the property that gives red-black trees their name — the colouring is what makes black-height uniform without keeping every path the same total length.

From rules 4 and 5 the height bound follows directly. The shortest root-to-NIL path is all black, of length bh (the black height). The longest is alternating black-red-black-red, of length at most 2·bh. So longest ≤ 2 × shortest — the tree is at most twice as deep on one side as the other, which bounds total height at 2 log₂(n + 1).

This is a looser balance than AVL trees (which keep |left-height − right-height| ≤ 1 per node), but it is enough to keep all operations at O(log n). The looser balance is exactly what makes red-black trees cheaper to maintain (fewer rotations per write), which is why they dominate when writes are frequent.

The red-black tree began life under a different name. Rudolf Bayer published Symmetric Binary B-trees: Data Structure and Maintenance Algorithms in Acta Informatica in 1972 — the same year as his other paper on the (multi-key) B-tree. The symmetric binary B-tree was a special case where each B-tree node held at most two keys, drawn as a small binary subtree with horizontal "red" links between siblings and vertical "black" links to children. The isomorphism with red-black trees is exact, but Bayer's notation didn't catch on.

Six years later Leonidas Guibas and Robert Sedgewick published A Dichromatic Framework for Balanced Trees at the 19th IEEE FOCS in 1978. Their paper recast Bayer's structure as a binary tree with a single bit of colour per node, gave it the now-standard name, and worked out the five-case insert and six-case delete algorithms in the form everyone uses today. The choice of "red" and "black" was apparently because those were the two pen colours readily available at the Xerox PARC laser printer they were using.

That detail (pen colours) is the kind of thing that should make you suspicious of the academic-mythology version of any data structure. The structure itself is older than the name; it had been studied for years under "symmetric binary B-tree" before Guibas and Sedgewick gave it the catchier label. The colouring is arbitrary too. You could equivalently mark each node with a single bit called "type 0 / type 1" or "open / closed" and the invariants would still bound the height. The colour metaphor is mnemonic; the math doesn't care.

The CLRS textbook (Introduction to Algorithms, Cormen-Leiserson-Rivest-Stein) gave red-black trees their canonical pedagogical treatment in 1990, with the five-case insert and six-case delete that's now reproduced everywhere. CLRS chapter 13 is the standard reference; every undergraduate course in data structures since has taught some flavour of that treatment. The Linux kernel's lib/rbtree.c credits "Introduction to Algorithms" in its header comment. Java's TreeMap implementation has the same lineage — Doug Lea's commit history references CLRS by chapter and verse.

A red-black insert begins as a plain BST insert. Walk down from the root, comparing keys, until you find an empty NIL slot; insert the new node there, coloured red. Red is the right default: a new red leaf preserves invariant 5 (black-height is unchanged on every path) and only risks violating invariant 4 (no two reds in a row). The fixup procedure exists to repair that violation when the new node's parent is also red.

The fixup walks up from the inserted node z, considering five cases keyed on the colour of z's uncle (the parent's sibling) and the local geometry. The cases are mirrored ("parent is left child of grandparent" and "parent is right child"), so they appear as ten in the textbook but really there are five.

1. Case 1: uncle red. Recolour parent and uncle to black, recolour grandparent to red, then repeat the fixup at the grandparent. The fix propagates two levels up the tree; height bound means this can happen at most log n times. No rotation involved.
2. Case 2: uncle black, z is the inner child. Rotate z's parent away from the grandparent (a left rotation if parent is left child, a right rotation if right child) to convert this into case 3.
3. Case 3: uncle black, z is the outer child. Recolour parent black and grandparent red; rotate at the grandparent toward the uncle. The fix terminates.

The asymmetry between case 1 and case 3 is the heart of the algorithm. When the uncle is red there's no rotation — the tree is "wide enough" that simply recolouring redistributes black-height. When the uncle is black the tree is "narrow" on that side and needs a rotation to redistribute keys laterally. Case 2 exists purely to normalise an inner-child geometry into an outer-child one so case 3 can finish.

The whole fixup is at most O(log n) work because case 1 propagates up one level at a time and cases 2 and 3 terminate immediately. In practice fixups are short: experimental measurements show the average insert performs fewer than 0.5 rotations, and over 90% of inserts complete with only constant-time recolouring. This is why red-black trees are popular for write-heavy workloads.

Red-black delete is harder than insert because removing a black node creates a black-height deficit that must be repaired along the path back to the root. The classical CLRS treatment models this with a fictitious "double-black" colour: when a black node is removed, the spot where it sat is treated as having two units of blackness, and the fixup walks up redistributing that extra black until it cancels out.

The delete itself runs the standard BST removal — if the target has two children, swap with the in-order successor and then delete that. The node finally removed has at most one real child. If that node was red, no invariant is broken (its parent and child were both black) and the delete terminates. If it was black, its replacement child inherits a "double-black" marker and the fixup procedure runs.

The fixup considers six cases keyed on the colour of the sibling and the colours of the sibling's children. Like insert, the cases come mirrored, so the textbook count of 6 reflects 3 cases × 2 mirrors.

1. Case 1: sibling red. Recolour sibling black, parent red, rotate parent toward the double-black side. The sibling that ends up adjacent to the double-black node is now guaranteed black; fall through to cases 2-4.
2. Case 2: sibling black with two black children. Recolour sibling red. This balances the black-heights on the two sides but adds one black to the parent (which absorbs the double-black). Continue the fixup at the parent.
3. Case 3: sibling black, inner child red, outer child black. Recolour the sibling red and its inner child black; rotate at the sibling. Falls through to case 4.
4. Case 4: sibling black, outer child red. Recolour sibling to parent's colour, parent black, outer red child black; rotate at parent. Fixup terminates.

The double-black model is bookkeeping, not a real colour stored in nodes. In practice an implementation passes around a pointer to the deficient node and its parent; when the deficit is resolved (case 4 fires, or case 2 propagates to the root), the markers go away. The Linux kernel's __rb_erase_color does it slightly differently — it considers eight cases with explicit left/right symmetry and avoids the conceptual double-black entirely. Both produce identical trees.

AVL trees, published by Adelson-Velsky and Landis in 1962, predate red-black trees by sixteen years. Both achieve O(log n) for search, insert, and delete. The difference is how strictly they enforce balance, and what they pay for that strictness.

AVL keeps the height difference between any node's two children at most 1. The worst-case height is 1.44 log₂(n + 2), slightly better than RB's 2 log₂(n + 1). For reads that matters a little: an AVL lookup costs about 28% fewer comparisons on a random-shaped tree. For applications where reads massively dominate, AVL wins.

The cost is paid at writes. AVL's tight balance means insertions and deletions can require rotations propagating all the way to the root in the worst case — O(log n) rotations per delete. Red-black's looser balance means at most two rotations per insert and at most three per delete, with the rest of the fixup being colour changes that are cheap pointer writes. For write-heavy workloads, RB wins by a large margin.

This is why production code with mixed read/write patterns tends to pick red-black: standard libraries (std::map, TreeMap), kernel data structures (Linux's CFS, EXT4 directory cache), and language runtimes (V8's OrderedHashMap internals). AVL appears more in pure-academic code, in some database index implementations (older versions of Sybase, Tandem NonStop), and in language libraries that prioritise read-only lookup tables.

There are other balanced BST options (weight-balanced trees, splay trees, treaps, scapegoat trees), but in the hierarchy of "things shipping in 2026," it's red-black for general purpose, B-trees for disk, skip lists for concurrent in-memory, and AVL for the niche where reads dominate so heavily that the 28% lookup advantage outweighs everything else.

The Linux Completely Fair Scheduler (CFS), introduced in kernel 2.6.23 (2007) and authored by Ingo Molnár, picks the next runnable task by finding the one with the smallest accumulated virtual runtime (vruntime). Internally CFS maintains a per-CPU run queue as a red-black tree keyed by vruntime. The leftmost node is the next task to run; selecting it is O(1) because CFS caches the leftmost pointer.

Why red-black and not a simpler structure? Three reasons that compound.

First, the workload is write-heavy. Every task that runs has its vruntime updated each time the scheduler tick fires (typically every 1-4 ms). On a busy server with hundreds of runnable tasks, that's hundreds of tree updates per millisecond. A structure with cheap writes is critical; a structure with expensive rebalances would consume scheduler latency budget.

Second, the operation set is the right shape. CFS needs ordered insertion, ordered deletion, and "find the minimum": exactly what a balanced BST handles efficiently. A min-heap would be cheaper for "find min" alone, but heaps don't support efficient deletion of an arbitrary key, which CFS needs when a task blocks or sleeps.

Third, predictability. The kernel scheduler must have bounded latency. A naive linked list would be O(n) per operation; an AVL tree would be O(log n) but with higher constants on writes; an LSM tree would have spiky compaction costs. Red-black gives flat O(log n) with no surprises. The kernel scheduler is exactly the kind of code where worst-case matters more than average-case.

The Linux rbtree implementation in lib/rbtree.c is worth reading directly. The header comment lists the invariants; the inline functions __rb_rotate_left and __rb_rotate_right are textbook; the colour bit is stolen from the low bit of the parent pointer to save 8 bytes per node. CFS itself lives in kernel/sched/fair.c and embeds struct rb_node inside struct sched_entity. The same rbtree.c is also used by EXT4's directory entry cache, the kernel's epoll interest list, the memory allocator's free-block index, and the deadline scheduler. One file, twenty consumers.

The C++ standard library specifies std::map and std::set as ordered associative containers with O(log n) worst-case lookup, insert, and delete. It also pins down iterator semantics: iterators must traverse in sorted order, and they must remain valid across all mutations except the deletion of the element they point to. Both major implementations implement these requirements with a red-black tree: libstdc++ (GCC's) and libc++ (Clang's).

Why not a hash table? Because std::map is the ordered map; std::unordered_map (C++11) is the hash-based one. Ordering is the whole point — std::map supports lower_bound, upper_bound, ordered iteration, range queries, and finds the closest key when an exact match fails. Hash tables can do none of these efficiently.

Why red-black specifically and not AVL? Two reasons. The first is iterator stability: an AVL tree's tighter rebalancing means more nodes shift positions per insert or delete, which would invalidate more iterators if implementations didn't already use parent pointers (both libstdc++ and libc++ do, so the invalidation guarantee is the same either way — but RB still rotates less). The second is the historical accident that the original HP and SGI STL implementations (Stepanov, Lee, Musser) used red-black, and every subsequent implementation followed.

Java's TreeMap tells a similar story. The Javadoc specifies O(log n) for the SortedMap operations; the implementation is a red-black tree authored by Josh Bloch in JDK 1.2 (1998) and substantially unchanged since. The JDK's own source comments cite CLRS chapter 13.

Red-black trees are notoriously difficult to make concurrent. The problem isn't reads (those can be served with hand-over-hand latching or RCU-style versioned snapshots) — it's writes. A single insert can trigger a cascade of recolours propagating up to the root; a single delete can require rebalancing along the whole path. Holding fine-grained locks during this cascade is hard because the locks must be acquired in the right order to avoid deadlock, and the cascade's shape isn't known until you're already partway up the tree.

Various lock-free or fine-grained-locking schemes have been proposed in the literature — Park & Hwang's relaxed-balance trees, Tsay & Li's concurrent RB tree, the Bronson et al. concurrent AVL tree from PPoPP 2010 — but none are widely deployed. Real concurrent code that needs ordered map semantics tends to reach for one of two alternatives.

The first is skip lists, which are much easier to make concurrent. Insertions only touch a few horizontal links and a few vertical levels; with a per-node mutex or even pure CAS, a skip list scales nearly linearly with cores. Java's ConcurrentSkipListMap, Doug Lea's lock-free skip list, is the standard concurrent ordered map in the JDK. Redis sorted sets, RocksDB memtables, LevelDB memtables, and the Linux kernel's IO scheduler all use skip lists for the same reason. (See the skip list simulator for the detail.)

The second is copy-on-write B-trees, which avoid the concurrency problem by never mutating in place. Updates clone the path from root to leaf; the new root atomically replaces the old via a single pointer swap. LMDB, BoltDB, etcd's bbolt, and FoundationDB's storage layer all use this approach. The cost is write amplification — every update touches log n pages — but the win is trivial concurrency: readers see consistent snapshots and writers serialize cleanly.

For single-threaded code or coarse-grained-locked code, red-black remains the right choice. The moment you need lock-free or fine-grained concurrent access to an ordered map, look elsewhere first.

Red-black implementations have a long history of subtle bugs. CLRS's first edition shipped with a delete bug in 1990; the fix appeared in errata. Java's TreeMap had a delete-rebalance bug filed as JDK-6480824 that lingered for years. Even Linux's rbtree.c has had several CVE-grade fixes over the kernel's lifetime. The same five mistakes appear over and over.

1. Off-by-one in the double-black propagation. The delete fixup loop terminates when the double-black node becomes red (paint it black, you're done) or when it reaches the root. Off-by-one bugs in the loop condition leave the tree with a phantom double-black somewhere, which silently violates invariant 5 and corrupts black-height bookkeeping.
2. Mis-colouring after rotation. Cases 3 and 4 of delete and cases 2 and 3 of insert do a recolour and a rotation; getting the colour assignments wrong (parent vs grandparent, before vs after rotation) produces a tree that looks balanced but isn't. The black-height check catches this quickly.
3. Forgetting to recolour the root black. Invariant 2 says the root is black; the fixup procedure can leave it red. Every textbook implementation ends with T.root.color = BLACK as the last line of insert and delete. Skip it, and the next operation that recurses on a red root subtree will fail an assertion.
4. NIL sentinel confusion. Many implementations use a single shared NIL sentinel object to represent all the leaves. Bugs arise when the sentinel's parent pointer gets temporarily set during a fixup, then read by another operation. The result is a tree that "has a NIL whose parent is some random node." Code reviews should look for any write to nil.parent.
5. Iterator invalidation after balanced rotation. If a library exposes iterators to RB nodes (like std::map::iterator), the iterator must remain valid across rotations. Most implementations achieve this by storing parent pointers in nodes and updating them on rotation; bugs appear when one of the parent updates is missed. The result: iterator-walk produces the wrong order after a rebalance.

The single most useful defensive measure is a post-condition checker: after every insert and delete in debug builds, walk the tree and assert all five invariants. The check is O(n) per operation, slow but acceptable in testing. Random-operation fuzzing finds every implementation bug within a few thousand operations once the checker is in place.

The two most useful red-black variants are Sedgewick's left-leaning red-black tree (LLRB) and the 2-3-4 tree isomorphism. Both exist to make the algorithm easier to implement correctly, with no asymptotic change to the operation costs.

Left-leaning red-black tree (Sedgewick, 2008). Adds a sixth invariant: red links must always lean left. This eliminates the right-leaning red subcase from every case in the classical algorithm, cutting the insert fixup down to one case and the delete fixup to about half its original size. The implementation in Sedgewick's Algorithms, 4th Edition textbook is about 100 lines of Java; the classical CLRS version is around 250 in C. The trade-off: LLRB rotates slightly more on average (because every right-leaning red has to be rotated into a left-leaning position immediately) and the height bound rises slightly. For pedagogical and correctness-critical code, LLRB is the right choice; for performance-critical kernel data structures, the classical RB is still preferred.

2-3-4 tree isomorphism. A red-black tree is exactly a 2-3-4 tree (B-tree of order 4) in disguise. Each black node corresponds to a 2-3-4 node, with adjacent red children "absorbed" into that node's key list. A 2-node has two children and one key; a 3-node has three children and two keys; a 4-node has four children and three keys, and you can read these off the red-black tree by walking through the black skeleton and merging in red descendants. This isn't just curiosity: it's how you derive the five invariants. The black-height invariant is the 2-3-4 "all leaves at same depth" property; the no-red-red invariant is the 2-3-4 "max three keys per node" property. Once you see the isomorphism, the red-black structure stops being arbitrary.

Persistent red-black tree. Clojure's PersistentTreeMap, Scala's TreeMap, and Haskell's Data.Map all implement persistent ordered maps with red-black trees. Persistence means every mutation returns a new tree that shares structure with the old; the path from root to modified leaf is cloned (O(log n) work) but the rest of the tree is shared. This is the structure-sharing trick from Okasaki's Purely Functional Data Structures; the red-black tree's bounded fixup makes it a natural fit.

Order-statistics red-black tree. Augment each node with the subtree size. After every rotation and recolour, update the augmented value. The tree now supports select(k) (find the k-th smallest element) and rank(x) (count elements less than x) in O(log n). Boost.Multi_index and several database query optimisers use this augmentation; the technique generalises to any associative aggregation over the tree.