subroute.
Advanced12 min readlive prototype

Red-Black Tree

Looser balancing through five color rules. Fewer rotations than AVL — which is why it's the tree inside your language's standard map and the Linux kernel.

Overview

What this concept solves

A red-black tree is a binary search tree that paints every node red or black and enforces five invariants that together guarantee the tree can never be more than twice as tall as the shortest root-to-leaf path. That height bound — ≤ 2·log₂(n+1) — means every search, insert, and delete costs O(log n) in the worst case, not just on average. Unlike a plain BST that degrades to a linked list on sorted input, a red-black tree will never do that.

The coloring scheme is the clever part. Red edges (or equivalently, red nodes) represent 'free' links that don't count toward balance; black edges are the ones that must balance perfectly across all root-to-NIL paths. The invariant that every such path has the same number of black nodes (the black-height) is what enforces balance. The rule that a red node's children must both be black prevents two reds from appearing in a row, which bounds how much extra height the red links can add. Taken together, the shortest possible path uses only black nodes (length = black-height), and the longest alternates red and black (length = 2 × black-height). The ratio is exactly 2.

Red-black trees sit at the center of systems programming. std::map and std::set in C++, java.util.TreeMap and java.util.TreeSet in Java, the Linux CFS process scheduler, epoll's event queue, and the kernel's virtual-memory area tracking all rely on red-black trees — specifically because red-black trees perform at most two rotations per insert and three per delete, which is fewer than AVL trees require under heavy write loads. The coloring trick trades a tiny amount of extra height for dramatically cheaper rebalancing.

Mechanics

How it works

The five invariants

  1. Every node is either red or black. (Color is a single bit.)
  2. The root is black. (Prevents a degenerate case in fixup and keeps the black-height accounting clean.)
  3. Every NIL leaf is black. (Sentinel leaves are conceptually black, so path lengths include them.)
  4. If a node is red, both its children are black. (No two consecutive red nodes — this is the 'no double-red' rule.)
  5. Every path from a given node down to any NIL descendant passes through the same number of black nodes. (This is the black-height invariant — it's what enforces balance.)

Why the invariants bound height

  • Let bh(x) be the black-height of node x (number of black nodes on any path from x to a NIL, not counting x itself). Every subtree rooted at x contains at least 2^bh(x) − 1 internal nodes.
  • Therefore n ≥ 2^bh(root) − 1, so bh(root) ≤ log₂(n+1).
  • The height h of the tree is at most 2·bh(root) (because the 'no double-red' rule means at most half of any root-to-leaf path's nodes can be red).
  • Combining: h ≤ 2·log₂(n+1) — a hard upper bound on tree height, not an average-case claim.

Insert fixup: the three cases

Insert the new node as red (preserving black-height). If its parent is black, done — no invariant is violated. If the parent is also red, you have a double-red and must fix it. Let z be the newly inserted (or just-fixed) red node, p its red parent, g the black grandparent, and u the uncle (g's other child):

  1. Uncle is red → recolor and climb. Flip p and u to black, flip g to red. Move the problem up: treat g as the new double-red node and repeat. This is a pure recolor — zero rotations.
  2. Uncle is black and z is a 'triangle' (z and p are on opposite sides of g) → rotate to a line. Rotate p in the direction toward g, turning the triangle into a line. Now apply case 3.
  3. Uncle is black and z is a 'line' (z, p, g are all on the same side) → rotate grandparent + recolor. Rotate g in the opposite direction (promoting p), then swap the colors of p and g. The double-red is resolved; no further propagation needed.

Why ≤ 2 rotations per insert

Case 1 (uncle red) propagates the fix upward but uses zero rotations. Cases 2 and 3 together use one or two rotations but immediately terminate — once you hit a black uncle, recoloring stops climbing. This is the key structural difference from AVL: AVL's double-rotation balancing can cascade up the tree, while red-black's rotation cases are always a local, bounded fix.

Delete fixup (overview)

  • Deletion is more complex — four cases instead of three — but the same bounding logic applies: at most three rotations for any delete.
  • The deleted node's 'missing' black is pushed down into a double-black placeholder and resolved by recoloring or rotating with siblings.
  • This prototype omits delete to keep the animation focused on the insert fixup cases; the Linux kernel's rb_erase implementation in lib/rbtree.c is the canonical reference.

Red-black vs AVL: when to reach for each

AVL trees maintain a stricter height bound (difference in subtree heights ≤ 1) and are therefore shorter on average — making them faster for read-heavy workloads. Red-black trees rebalance with fewer rotations and are faster under write-heavy workloads, which is why operating-system schedulers and standard-library ordered maps default to them.

Interactive prototype

Run it. Break it. Tune it.

Sandboxed simulation embedded right in the page. No setup, no install.

About this simulation

A live red-black tree that grows as you insert values. Type a number and press Insert to add a node — the fixup animation highlights the focus node in yellow and steps through recolors and rotations one by one. Random inserts a random integer; Reset clears the tree. Use the Speed slider to slow the animation to a crawl so you can trace each fixup case. The Sequential insert 1→7 demo builds a worst-case ascending sequence and shows how the tree rebalances without the pathological skew you'd get from a plain BST. The Recolor then rotate (50,30,70,20,40,10) demo exercises both fixup branches — first a recolor-and-climb, then a triangle rotation, then a line rotation — so you see all three cases in one run. Stats in the corner track nodes, height, recolors, and rotations in real time.

Hands-on

Try these on your own

Open the prototype above, run each experiment, predict the answer, then verify.

try 01

Sequential insert 1→7 — watch the tree rebalance

Press the Sequential insert 1→7 demo button. A plain BST fed the values 1, 2, 3, 4, 5, 6, 7 in order degrades to a right-leaning chain — O(n) height. Watch what the red-black fixup does instead: after inserting 1 and 2 (red), inserting 3 triggers a line rotation on the grandparent (case 3), promoting 2 to the root and recoloring. By the time all 7 nodes are in, the tree is balanced to height 3. Notice the rotations counter: you'll see exactly 3 rotations for 7 inserts, confirming the ≤ 2-per-insert bound holds in practice.

try 02

Recolor then rotate — trace all three fixup cases

Press Recolor then rotate (50,30,70,20,40,10). Insert 50 (root, forced black), 30 (red, left child — OK), 70 (red, right child — OK). Now insert 20: parent 30 is red, uncle 70 is also red → case 1 recolor: flip 30 and 70 to black, flip 50 to red, then re-blacken 50 (it's the root). Insert 40: parent 30 is black — no fixup. Insert 10: parent 20 is red, uncle 40 is black, 10 is a left child of a left child → case 3 line rotation: rotate 30 right, recolor. Watch the recolors and rotations counters increment at each step. Slow the speed slider to 1× to see every individual transition.

try 03

Insert your own sequence and verify black-height

Type any integers into the input and press Insert one by one. After each insert, count the black nodes on any root-to-NIL path — they must all be equal. Try a sequence that forces a triangle fixup (case 2): insert 10, 30, 20. The value 20 is a right child of left child (a triangle); watch it trigger a left rotation on 30 first (case 2), then a right rotation on 10 (case 3). The height stat in the corner should never exceed ⌊2·log₂(n+1)⌋ regardless of what order you insert.

try 04

Free play — try to break the invariants

Press Random repeatedly to load random values and watch how the tree stays balanced no matter what. Then try adversarial sequences: purely descending order (100, 90, 80, …) or alternating high-low (50, 1, 100, 2, 99, 3, …). Compare the height and rotations stats across sequences. Notice that descending order drives the most rotations (every other insert needs a line rotation) while the alternating sequence triggers more recolors. The black-height should remain consistent and height should stay well under 2·log₂(n+1) in every case — that bound is provable, not a coincidence.

In practice

When to use it — and what you give up

Where red-black trees excel

  • Write-heavy ordered maps — standard library std::map/TreeMap style containers where inserts and deletes are frequent; the low rotation count matters.
  • Real-time systems — the worst-case O(log n) guarantee (not amortized) fits schedulers and interrupt handlers that can't tolerate spikes.
  • Operating system internals — Linux CFS (process scheduling), epoll (I/O event tracking), and vm_area_struct (virtual memory layout) all use red-black trees for deterministic O(log n) updates on kernel paths.
  • Interval trees and augmented BSTs — red-black structure is easy to augment with extra metadata (subtree max endpoint, size) without breaking the O(log n) guarantee.
  • Any 'ordered set with dynamic membership' — if you need sorted iteration and cheap insert/delete, red-black is the textbook answer.

When to consider alternatives

  • Read-heavy workloads with rare writes — an AVL tree is shorter (stricter balance) and slightly faster for lookups. Use AVL if searches vastly outnumber inserts and deletes.
  • Range queries on disk — B-trees (or B+ trees) have much higher branching factors and align with page sizes, making them dramatically faster when data doesn't fit in RAM.
  • Approximate membership — a Bloom filter or skip list may be simpler and fast enough; reserve red-black for when you need exact, ordered access.
  • Concurrent access — red-black trees require careful locking; lock-free skip lists are often simpler to reason about in multithreaded contexts.
  • Static data — if you build once and only query, a sorted array with binary search beats every balanced BST on cache locality and constant factors.

Pros

  • Guaranteed O(log n) worst case for search, insert, and delete — no degenerate cases, no amortized hand-waving.
  • Fewest rotations of any balanced BST — at most 2 per insert, 3 per delete. This is why write-heavy systems (OS schedulers, ordered maps) prefer red-black over AVL.
  • Simple augmentation — a single extra color bit per node; augmenting with size, max, or sum fields for interval trees or order-statistics trees is straightforward.
  • Universal availability — every major standard library ships a red-black tree (std::map, TreeMap, Python's sortedcontainers under the hood); well-understood, battle-tested code.
  • Deterministic rebalancing — fixup terminates in O(1) rotations (the rotation cases do not propagate); only the recolor case propagates, and it propagates without rotations.

Cons

  • More complex than AVL to implement correctly — five invariants, three insert-fixup cases, four delete-fixup cases, and symmetric mirror cases for each. Getting it right from scratch takes care.
  • Slightly taller than AVL — the weaker balance criterion means red-black trees can be up to 2× taller than AVL trees, so lookups have a larger constant factor.
  • Extra memory per node — one color bit (usually padded to a full byte or stored in a pointer's low bit as Linux does). Minor, but non-zero.
  • No efficient split/merge — unlike treaps or weight-balanced trees, splitting or merging two red-black trees at a key is non-trivial and O(log n) rather than O(1).
  • Harder to reason about correctness — the invariants interact subtly; it's easy to write fixup code that passes unit tests but breaks a corner case (e.g., inserting into an all-red path).

Reference

Code & further reading

A minimal reference implementation and pointers worth bookmarking.

red-black-insert.ts
type Color = "RED" | "BLACK";

interface RBNode {
  key: number;
  color: Color;
  left: RBNode | null;
  right: RBNode | null;
  parent: RBNode | null;
}

function newNode(key: number): RBNode {
  return { key, color: "RED", left: null, right: null, parent: null };
}

function rotateLeft(tree: { root: RBNode | null }, x: RBNode): void {
  const y = x.right!;
  x.right = y.left;
  if (y.left) y.left.parent = x;
  y.parent = x.parent;
  if (!x.parent) tree.root = y;
  else if (x === x.parent.left) x.parent.left = y;
  else x.parent.right = y;
  y.left = x;
  x.parent = y;
}

function rotateRight(tree: { root: RBNode | null }, x: RBNode): void {
  const y = x.left!;
  x.left = y.right;
  if (y.right) y.right.parent = x;
  y.parent = x.parent;
  if (!x.parent) tree.root = y;
  else if (x === x.parent.right) x.parent.right = y;
  else x.parent.left = y;
  y.right = x;
  x.parent = y;
}

function insertFixup(tree: { root: RBNode | null }, z: RBNode): void {
  while (z.parent?.color === "RED") {
    const p = z.parent!;
    const g = p.parent!;
    if (p === g.left) {
      const uncle = g.right;
      if (uncle?.color === "RED") {          // Case 1: uncle red → recolor
        p.color = "BLACK";
        uncle.color = "BLACK";
        g.color = "RED";
        z = g;                               // climb up
      } else {
        if (z === p.right) {                 // Case 2: triangle → rotate to line
          z = p;
          rotateLeft(tree, z);
        }
        z.parent!.color = "BLACK";           // Case 3: line → rotate grandparent
        z.parent!.parent!.color = "RED";
        rotateRight(tree, z.parent!.parent!);
      }
    } else {                                 // Mirror: p is g.right
      const uncle = g.left;
      if (uncle?.color === "RED") {
        p.color = "BLACK"; uncle.color = "BLACK"; g.color = "RED"; z = g;
      } else {
        if (z === p.left) { z = p; rotateRight(tree, z); }
        z.parent!.color = "BLACK";
        z.parent!.parent!.color = "RED";
        rotateLeft(tree, z.parent!.parent!);
      }
    }
  }
  tree.root!.color = "BLACK";               // Invariant 2: root is always black
}

function insert(tree: { root: RBNode | null }, key: number): void {
  const z = newNode(key);
  let y: RBNode | null = null;
  let x = tree.root;
  while (x) { y = x; x = key < x.key ? x.left : x.right; }
  z.parent = y;
  if (!y) tree.root = z;
  else if (key < y.key) y.left = z;
  else y.right = z;
  insertFixup(tree, z);
}

References & further reading

7 sources

Knowledge check

Did the prototype land?

Quick questions, answers revealed on submit. No scoring saved.

question 01 / 03

A red-black tree has black-height 3 (three black nodes on every root-to-NIL path). What is the maximum possible height of the tree?

question 02 / 03

During an insert fixup, the newly inserted node's uncle is red. What happens?

question 03 / 03

Why do operating-system schedulers (like Linux CFS) prefer red-black trees over AVL trees?

0/3 answered

Was this concept helpful?

Tell us what worked, or what to improve. We read every note.

Back to Trees