Red-Black Trees

The 10-second versionCopy Anchor Link

An AVL tree keeps itself as short as possible, which is wonderful for lookups — but it pays for that tightness with rotations on every write, sometimes all the way up the tree. A red-black tree asks for something looser: don't chase perfect balance, just keep every root-to-leaf path within a factor of two of every other. It achieves this with a single extra bit per node — a colour (red or black) — and a small set of rules. The tree ends up slightly taller than AVL, but writes are cheaper, because most fixes are just recolouring and only occasionally a rotation. That balance of trade-offs is why it, not AVL, is what almost every standard library actually ships.

Why this existedCopy Anchor Link

Remember what AVL is optimizing: the shortest possible tree. A balance factor capped at ±1 means every search touches as few nodes as a BST can. But there's a hidden bill. To maintain that strictness, an insert can trigger rotations that ripple up the tree — every write risks paying for the tidiness the reads benefit from.

By the early 1970s, with disk and main-memory files in mind, Rudolf Bayer at Boeing's Scientific Research Labs was chasing a different goal: a balanced tree that is cheap to update. In 1972 he published a structure he called the symmetric binary B-tree — a clever way to squeeze a multi-key B-tree node (imagine a node that can hold two or three keys and three or four children) into an ordinary binary node by allowing some parent-child links to be "horizontal." It worked, but the two kinds of links made the diagrams and proofs a headache.

Six years later, in 1978, Leo Guibas and Robert Sedgewick found the presentation that stuck: colour the nodes red or black, and let a red node mean "this node is glued to its black parent, together they form one logical multi-key node." Suddenly the rules were visual — no red node may have a red child, and every path down has the same count of black nodes — and the structure got a memorable new name: the red-black tree.

Why it mattered: it made balanced trees cheap enough to use everywhere. If rebalancing costs almost nothing per write, you can put an ordered map in a standard library and never think about it again.

Inside the inventor's headCopy Anchor Link

Here's the tension Bayer was staring at. The B-tree gets its balance from height, not from tight fits: every leaf sits at the same depth, so no path is much longer than any other. That's a wonderfully cheap thing to maintain. But a B-tree node holds many keys, which is right for disk and awkward to reason about in memory. Could you get B-tree-grade balance with plain binary nodes?

Bayer's trick: allow certain links to be "horizontal," so a parent and one child together act as a single multi-key node. The problem was purely human — which links are horizontal, drawn plainly, is easy to lose track of. The algorithm was fine; the picture was confusing.

Guibas and Sedgewick's pivot was a change of notation, and it turned out to be the whole insight. Instead of "horizontal links," say: a red node hangs off a black parent, and together they are one B-tree node. Now everything Bayer proved becomes a glance:

The "aha" is that you never needed perfect balance. You needed two weaker, cheaper facts: no red node has a red child, and every path has the same number of black nodes. The first keeps redness from piling up; the second keeps paths from diverging by more than a factor of two. And crucially, both can be checked and repaired locally, so you never walk the whole tree.

That's the whole shift from AVL to red-black in one line: AVL checks a balance number everywhere; red-black checks a colour rule locally. Here's the difference in what you have to inspect after a write:

// Naive: after a write, walk the WHOLE tree hunting for an unbalanced node.// Correct, but O(n) — and you'd be doing it after every single insert.function check(n) {  if (!n) return 0;  const l = check(n.left), r = check(n.right);  if (Math.abs(l - r) > 1) console.log("unbalanced at", n.key);  return 1 + Math.max(l, r);}

// Improved: balance becomes a LOCAL test. A red node under a red parent is the// only defect that matters — you look at the node and its parent, nothing else.const violates = (n) => !!n && n.red && !!n.parent && n.parent.red;

The final approachCopy Anchor Link

The five colour invariantsCopy Anchor Link

A red-black tree is a BST satisfying all five of these at every moment:

1. Every node is red or black. (One bit of extra data per node.)
2. The root is black.
3. Every leaf is black. (The empty NIL slots count as black leaves.)
4. No red node has a red child. Red never appears twice in a row on any path.
5. Every path from a node down to a NIL leaf has the same number of black nodes — the black-height.

Rule 5 is the balance engine. If every root-to-leaf path has the same number of black nodes, and rule 4 guarantees no path can have more than twice the black count in total length, then the longest path is at most twice the shortest. That caps the height at 2 · log₂(n + 1) — not as tight as AVL's 1.44 · log₂ n, but comfortably logarithmic, and much cheaper to maintain.

The algorithm, as a flowCopy Anchor Link

Insertion is an ordinary BST insert, then a local repair that walks back up the one path it touched:

The genius is in that first branch: when the uncle is red, you fix the violation by flipping colours — no pointer surgery at all. Rotations are the exception, not the norm, and at most a constant number happen per insert. That's the "cheap writes" promise made concrete.

Left-leaning red-black trees (the intuition)Copy Anchor Link

Robert Sedgewick later realized you could forbid the messy cases entirely by requiring every red link to lean left — a node may be a red left child, never a red right child. He called the result a left-leaning red-black (LLRB) tree. The payoff is stunning: the entire insert collapses to three little rules applied on the way back up, and it maps one-to-one onto a 2-3-4 tree.

That is genuinely the whole algorithm — no case table, no uncle-hunting. It's why LLRB trees are the version people memorize.

A worked traceCopy Anchor Link

Insert 10, 20, 30 into an empty red-black tree, tracking colour:

• 10 becomes the root and is black (rule 2).
• 20 arrives red, as 10's right child. In LLRB we rotate it left so redness leans left: 20 becomes the root (black), 10 its red left child.
• 30 arrives red as 20's right child. That's a red right-link → rotate left at 20: 30 becomes the root (black), 20 red-left, and the left-leaning rule is satisfied.

The tree is a three-node column with a black root — height 2, and every path has exactly one black node. Compare that to the plain BST, which would have made 10 → 20 → 30 a degenerate chain.

It in codeCopy Anchor Link

The complete left-leaning red-black insert: rotations, the colour flip, and the three fix-up rules.

class Node {  constructor(key, red) { this.key = key; this.red = red; this.left = null; this.right = null; }}const isRed = (n) => !!n && n.red;function rotateLeft(h) {  const x = h.right;  h.right = x.left;  x.left = h;  x.red = h.red;           // the subtree keeps its colour  h.red = true;            // the displaced node goes red  return x;}function rotateRight(h) {  const x = h.left;  h.left = x.right;  x.right = h;  x.red = h.red;  h.red = true;  return x;}function flipColors(h) {  h.red = !h.red;  h.left.red  = !h.left.red;  h.right.red = !h.right.red;}function insert(h, key) {  if (!h) return new Node(key, true);              // new nodes start red  if (key < h.key)      h.left  = insert(h.left, key);  else if (key > h.key) h.right = insert(h.right, key);  else                  return h;                  // no duplicates  if (isRed(h.right) && !isRed(h.left))          h = rotateLeft(h);   // lean left  if (isRed(h.left) && isRed(h.left.left))       h = rotateRight(h);  // balance a 4-node  if (isRed(h.left) && isRed(h.right))           flipColors(h);        // split the 4-node  return h;}

Cost tableCopy Anchor Link

This is the trade in one table. Reads: AVL's tighter tree wins slightly. Writes: red-black's relaxed rules win clearly, because most inserts are fixed by a colour flip and at most a constant number of rotations. When you have to pick one for a general-purpose library, "fast enough reads and cheap writes" beats "fastest reads and expensive writes."

Where you meet it todayCopy Anchor Link

• C++ standard library. std::map, std::set, std::multimap, and std::multiset are (on essentially every mainstream implementation) red-black trees — that's why they promise O(log n) operations with sorted iteration.
• Java's collections. TreeMap and TreeSet are red-black trees, giving you the ordered floorKey, ceilingKey, and subMap operations plain hash maps can't.
• The Linux kernel. The scheduler, the virtual-memory area lists, and timers use lib/rbtree.c — millions of machines rebalance red-black trees many times a second, all silently.
• .NET. SortedDictionary and SortedSet are red-black trees too; if it's an ordered container in a standard library, red-black is the safe bet.

// Build an ordered map from arbitrary keys, then read the keys in sorted order.// The tree guarantees O(log n) inserts AND a sorted inorder walk, for free.let root = null;for (const k of [7, 3, 9, 1, 8, 5]) root = insert(root, k);inorder(root);          // 1 3 5 7 8 9 — sorted, and guaranteed shallow

RecapCopy Anchor Link

• A red-black tree is a BST plus one colour bit per node and five invariants; the key two are no red-red parent-child pairs and equal black-height on every path.
• Those rules keep the height within 2 · log₂(n + 1) — looser than AVL, but genuinely logarithmic.
• Fixes are local: recolour when the uncle is red, rotate otherwise; at most O(1) rotations per insert.
• Left-leaning red-black trees (Sedgewick) restrict red links to lean left and collapse the whole algorithm into three rules.
• Versus AVL: slightly slower reads, much cheaper writes — which is why std::map, TreeMap, and the Linux kernel chose it.

Next up: B-Trees & B+ Trees — the same balance idea, but built to tame a much slower device than RAM.