Red-Black Tree

A red-black tree (RB tree) is a self-balancing Binary Search Tree in which every node carries a color — red or black — that, together with a small set of structural invariants, guarantees the tree’s height is at most 2 · log₂(n + 1). RB trees were introduced by Rudolf Bayer in 1972 (under the name symmetric binary B-trees) as a way to give B-trees binary structure; Guibas and Sedgewick re-framed and renamed them in 1978 with the now-standard color metaphor and the five invariants that every interview candidate is expected to recite. Compared to AVL Trees, RB trees enforce a looser balance — height up to 2·log n vs AVL’s 1.44·log n — but pay for it with fewer rotations on insert and delete (at most 2 rotations per insert, at most 3 per delete, vs AVL’s potentially-cascading delete). This trade-off makes RB trees the de facto balanced BST in production code: Java’s TreeMap and TreeSet, C++ STL’s std::map / std::set / std::multimap, the Linux kernel’s Completely Fair Scheduler (CFS) and epoll ready-list, and the Linux memory-management VMA tree all use red-black trees or close cousins. (Not every “sorted container” is a red-black tree: Python’s third-party sortedcontainers library, for instance, deliberately uses a list-of-lists / sorted-list structure rather than any balanced tree, on the grounds that CPython’s C-level list operations and bisect.insort outperform per-node-pointer trees in practice — see Sorted Containers implementation notes.) The five invariants are non-obvious; once internalized, every operation reduces to “fix any invariant violations and color-flip / rotate as needed.”

1. Intuition — A B-Tree Disguised as a Binary Tree

Bayer’s 1972 paper called these “symmetric binary B-trees” because that’s exactly what they are: a 2-3-4 B-Tree of order 4, encoded as a binary tree where each B-tree node of k keys becomes k red-black nodes — the “leader” colored black, its companions colored red. Each black node represents the root of a B-tree node; each red node represents an additional key glued onto its parent’s B-tree node.

This isomorphism is the cleanest way to grasp red-black trees. A B-tree of order 4 has the property that every leaf is at the same depth (perfectly height-balanced). When we squint at the binary-tree encoding, we see: the black-depth (number of black nodes on any root-to-leaf path) is the same everywhere — that’s the perfect-balance property of the underlying B-tree. The red nodes are “free riders”: they can be sprinkled in to flatten a black 1-2-3 child structure into binary form. As long as we don’t have consecutive red nodes (which would correspond to a B-tree node of more than 4 keys), the B-tree’s balance is preserved.

So the five invariants of red-black trees (§2) all boil down to “this is a valid 2-3-4 B-tree in disguise.” The “no two consecutive reds” rule keeps each B-tree node from overflowing. The “all paths have the same black depth” rule is the B-tree’s perfect-balance property restated.

The real-world analogy: imagine a corporate org chart where every team must have between 1 and 3 reports (a 2-3-4 B-tree node), but you’re stuck visualizing it on a binary org-chart software. You designate one report as “primary” (black) and treat the others as “lateral peers” (red) attached to the primary. The “no two reds in a row” rule is “no peer-of-a-peer arrangements”; the “same number of blacks per root-to-leaf path” rule is “every team has equal management depth.” Restructuring the underlying team structure (a B-tree split or merge) corresponds to the red-black tree’s rotations and recolorings.

The looser balance (compared to AVL Tree) is what gives RB its production-friendliness. Insert and delete each do at most O(1) rotations (specifically: ≤ 2 for insert, ≤ 3 for delete) plus O(log n) recolorings. AVL can require up to O(log n) rotations on delete. For workloads heavy on writes, that constant-factor difference adds up.

2. The Five Invariants

A binary search tree is a red-black tree if and only if all of the following hold:

1. Every node is either red or black.
2. The root is black.
3. Every leaf (the conceptual “NIL” sentinel) is black. (Many implementations use a single shared NIL sentinel for all leaves; it simplifies the cases.)
4. If a node is red, both of its children are black. (Equivalently: no two consecutive red nodes on any path.)
5. For each node, every simple path from that node to any descendant leaf contains the same number of black nodes. (This is the black-height invariant.)

The black-height of a node v, denoted bh(v), is the number of black nodes on any path from v (not counting v itself) down to a leaf. By invariant 5, all such paths have the same count. The black-height of the tree is bh(root).

2.1 Why these five, specifically?

Each invariant has a clear purpose:

• Invariant 1 is the typing constraint — every node has a color slot.
• Invariant 2 (root is black) is a normalization: it lets us flip the root’s color freely during fix-up without consequences.
• Invariant 3 (NIL is black) defines the base case for the black-height count. Without this, “black height = 0” wouldn’t mean what we want at leaves.
• Invariant 4 (no two reds in a row) bounds the maximum path length: at most every other node on a path can be red, so the longest path has at most twice as many nodes as the shortest.
• Invariant 5 (equal black height) bounds the minimum path length: every path has the same number of black nodes, so the shortest path is at least bh(root) long.

Combining 4 and 5: the shortest path from root to leaf has length ≥ bh(root) (all blacks); the longest has length ≤ 2 · bh(root) (alternating black-red). So no path is more than 2× the length of any other — that’s the height bound (§5.1).

2.2 The B-tree mapping (Bayer 1972)

2-3-4 B-tree node	Red-black equivalent
Single-key node	Black node
Two-key node	Black node + 1 red child (left or right)
Three-key node	Black node + 2 red children (one each side)

A B-tree split (when a 4-key node would form) corresponds to a recoloring (push the middle key up by recoloring it black, the children red) — exactly the standard “Case 1” of red-black insertion fix-up. A B-tree merge corresponds to the “sibling-with-black-children” delete case.

3. Tiny Worked Example — Insertion Triggering Recolor and Rotation

Insert 10, 20, 30, 15, 25, 5, 35, 18 into an initially empty RB tree. Every newly inserted node starts red, then we walk back up fixing violations.

3.1 Insert 10

Empty tree → 10 is the root → recolor to black (invariant 2).

10·B

3.2 Insert 20

10·B
  \
  20·R

20 is red, its parent 10 is black: no consecutive reds. Black-heights equal (both leaves have black-height 1, since the conceptual NILs are black). All invariants hold.

3.3 Insert 30 — single rotation

10·B
  \
  20·R
    \
    30·R    ← VIOLATION: red parent (20·R) and red child (30·R)

Two consecutive reds. The fix-up consults 30’s uncle (the sibling of its parent) — 10’s left child, which is NIL → “uncle is black.”

When the uncle is black and the new node is the right child of a right child (or any “straight line” case), we do a single rotation at the grandparent + recolor.

Apply: left-rotate at 10. Then recolor 20 to black and 10 to red:

   20·B
   /  \
 10·R  30·R

Black-heights are equal (every path has one black). No two consecutive reds. ✓

3.4 Insert 15

   20·B
   /  \
 10·R  30·R
   \
   15·R    ← VIOLATION

15’s parent is 10·R, grandparent is 20·B. 15’s uncle is 30·R — uncle is red.

When the uncle is red, we recolor (no rotation needed): flip parent and uncle to black, grandparent to red, and recursively check the grandparent for further violations.

   20·R         ← grandparent now red
   /  \
 10·B  30·B    ← parent and uncle now black
   \
   15·R

But now invariant 2 says the root must be black. So recolor 20 back to black (root special case):

   20·B
   /  \
 10·B  30·B
   \
   15·R

All invariants restored. ✓

3.5 Insert 25

       20·B
      /    \
    10·B   30·B
       \   /
      15·R 25·R

25 is red, parent 30·B is black. No violation.

3.6 Insert 5

       20·B
      /    \
    10·B   30·B
    /  \   /
   5·R  15·R 25·R

5 is red, parent 10·B is black. No violation.

3.7 Insert 35

       20·B
      /    \
    10·B   30·B
    / \    /  \
   5·R 15·R 25·R 35·R

35 is red, parent 30·B is black. No violation.

3.8 Insert 18 — recolor cascading up

Insert 18 as right child of 15·R:

       20·B
      /     \
    10·B    30·B
    / \     /  \
   5·R 15·R 25·R 35·R
         \
        18·R    ← VIOLATION

18’s parent is 15·R, grandparent is 10·B. Uncle is 5·R — red uncle.

Recolor: parent and uncle to black, grandparent to red:

       20·B
      /    \
    10·R   30·B    ← grandparent flipped red
    / \    /  \
   5·B 15·B 25·R 35·R    ← parent + uncle flipped black
         \
        18·R

Now check the new red — 10·R. Its parent is 20·B — no violation. ✓

The crucial thing to verify is that this recolor preserves the black-height invariant — that is the entire reason the red-uncle case is a legal fix. Trace any root-to-leaf path that passes through 10. Before the recolor, 10 was black and its children 5, 15 were red, so the count of black nodes from the root down to a leaf below 10 was: 20·B (1) + 10·B (1) + the black NILs below = a fixed total. After the recolor, 10 is red and 5, 15 are black: we removed one black at 10 but added one black at the level of 5/15, so the per-path black count is identical. The same holds for every path through the subtree — recoloring in this case redistributes blackness one level up without changing any path’s black total. (If it did change a path’s black total, invariant 5 would be violated and the “fix” would itself be a bug.) What does change is the location of the potential red-red violation: it moves up to 10, where we re-check against 10’s parent. Here 10’s parent 20 is black, so we are done; in general the loop continues climbing. This is why the red-uncle case is the “B-tree node split pushed up” step.

The full sequence above demonstrates uncle-red recoloring (step 3.4, 3.8) and uncle-black rotation (step 3.3). These are the two possibilities for every red-red violation; the next section systematizes them.

4. Algorithm — Insert and Fix-Up

4.1 Insert (BST descent + always-red leaf)

Identical to Binary Search Tree insertion, except: the new node is colored red. Then call fix-up.

RBInsert(T, key):
    z := new Node(key, color=RED, left=NIL, right=NIL)
    BSTInsert(T, z)        # standard BST insert; z lands at a leaf position
    RBInsertFixUp(T, z)

4.2 Insert fix-up — the three cases (and their symmetric mirrors)

The fix-up walks up from z, fixing red-red violations until it hits a black ancestor (no violation) or the root (recolor root to black).

RBInsertFixUp(T, z):
    while z.parent.color == RED:
        if z.parent == z.parent.parent.left:
            y := z.parent.parent.right                 # uncle (right side)
            if y.color == RED:
                # Case 1: uncle is red — recolor and recurse upward.
                z.parent.color := BLACK
                y.color := BLACK
                z.parent.parent.color := RED
                z := z.parent.parent
            else:
                if z == z.parent.right:
                    # Case 2: zigzag — rotate parent left to make it case 3.
                    z := z.parent
                    LeftRotate(T, z)
                # Case 3: straight line — rotate grandparent right + recolor.
                z.parent.color := BLACK
                z.parent.parent.color := RED
                RightRotate(T, z.parent.parent)
        else:
            # Symmetric: parent is right child of grandparent.
            (mirror of above with left ↔ right)
    T.root.color := BLACK

The three cases:

Case 1: Uncle is red. Recolor parent and uncle to black, grandparent to red. Then move up: the grandparent might now have a red parent → continue fixing. This is the “B-tree node split” case.

Case 2: Uncle is black, z is on the “inner” side. First rotate at parent to make it “Case 3” — straighten the zigzag.

Case 3: Uncle is black, z is on the “outer” side. Rotate at grandparent and swap parent/grandparent colors. After this, no further violation can exist above (grandparent is now black where parent used to be red).

Each case (1) recurses up by 2 levels (Case 1) or (2) terminates after 1–2 rotations (Cases 2, 3). So the total work is O(log n) time + at most 2 rotations per insert.

4.3 Delete — sketch (full code is mechanical but ~80 lines)

Standard BST delete logic: find the node, splice with successor if needed. The complication: if the spliced-out node was black, the black-height invariant is now violated (one path has one fewer black). We “push” the missing black down or absorb it via the four delete fix-up cases — symmetric to insert but with a different case structure on the deleted node’s sibling and the sibling’s children.

The delete fix-up has four cases (and four symmetric mirrors):

Case 1: Sibling is red. Rotate at parent + recolor → reduces to one of Cases 2/3/4 with a black sibling.

Case 2: Sibling is black, both sibling’s children are black. Recolor sibling red, push the “extra black” up to parent, recurse.

Case 3: Sibling is black, sibling’s near child is red, far child is black. Rotate at sibling to convert to Case 4.

Case 4: Sibling is black, sibling’s far child is red. Rotate at parent + recolor → done.

At most 3 rotations per delete. Like insert, total work is O(log n) due to the recoloring climb.

5. Python Implementation

A working insertion-only RB tree (full delete is ~80 more lines and not pedagogically illuminating once insert is understood):

from dataclasses import dataclass, field
from typing import Optional
 
RED = True
BLACK = False
 
@dataclass
class RBNode:
    key: int
    color: bool = RED
    left: Optional["RBNode"] = None
    right: Optional["RBNode"] = None
    parent: Optional["RBNode"] = None
 
class RedBlackTree:
    def __init__(self) -> None:
        # Sentinel NIL — single shared black "leaf" simplifies fix-up cases.
        self.NIL = RBNode(key=0, color=BLACK)
        self.root: RBNode = self.NIL
 
    def _rotate_left(self, x: RBNode) -> None:
        """Left rotation: y = x.right becomes x's parent."""
        y = x.right
        assert y is not None and y is not self.NIL
        x.right = y.left
        if y.left is not self.NIL:
            assert y.left is not None
            y.left.parent = x
        y.parent = x.parent
        if x.parent is None or x.parent is self.NIL:
            self.root = y
        elif x is x.parent.left:
            x.parent.left = y
        else:
            x.parent.right = y
        y.left = x
        x.parent = y
 
    def _rotate_right(self, x: RBNode) -> None:
        """Right rotation — symmetric to _rotate_left."""
        y = x.left
        assert y is not None and y is not self.NIL
        x.left = y.right
        if y.right is not self.NIL:
            assert y.right is not None
            y.right.parent = x
        y.parent = x.parent
        if x.parent is None or x.parent is self.NIL:
            self.root = y
        elif x is x.parent.right:
            x.parent.right = y
        else:
            x.parent.left = y
        y.right = x
        x.parent = y
 
    def insert(self, key: int) -> None:
        """Insert `key`; duplicates are silently no-op."""
        # Standard BST descent.
        z = RBNode(key=key, color=RED, left=self.NIL, right=self.NIL)
        y: Optional[RBNode] = None
        x: Optional[RBNode] = self.root
        while x is not self.NIL and x is not None:
            y = x
            if z.key < x.key:
                x = x.left
            elif z.key > x.key:
                x = x.right
            else:
                return
        z.parent = y
        if y is None:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z
        self._insert_fixup(z)
 
    def _insert_fixup(self, z: RBNode) -> None:
        """Restore RB invariants after inserting red node z."""
        while z.parent is not None and z.parent.color == RED:
            assert z.parent.parent is not None       # red parent ⇒ has a (black) grandparent
            grandparent = z.parent.parent
            if z.parent is grandparent.left:
                uncle = grandparent.right
                if uncle is not None and uncle.color == RED:
                    # Case 1: uncle red — recolor + climb.
                    z.parent.color = BLACK
                    uncle.color = BLACK
                    grandparent.color = RED
                    z = grandparent
                else:
                    if z is z.parent.right:
                        # Case 2: zigzag — left-rotate parent to straighten.
                        z = z.parent
                        self._rotate_left(z)
                    # Case 3: straight line — recolor + right-rotate grandparent.
                    assert z.parent is not None and z.parent.parent is not None
                    z.parent.color = BLACK
                    z.parent.parent.color = RED
                    self._rotate_right(z.parent.parent)
            else:
                # Mirror image: parent is right child of grandparent.
                uncle = grandparent.left
                if uncle is not None and uncle.color == RED:
                    z.parent.color = BLACK
                    uncle.color = BLACK
                    grandparent.color = RED
                    z = grandparent
                else:
                    if z is z.parent.left:
                        z = z.parent
                        self._rotate_right(z)
                    assert z.parent is not None and z.parent.parent is not None
                    z.parent.color = BLACK
                    z.parent.parent.color = RED
                    self._rotate_left(z.parent.parent)
        self.root.color = BLACK
 
    def in_order(self, node: Optional[RBNode] = None) -> list[int]:
        """Return keys in sorted order — exercises that BST property holds."""
        if node is None:
            node = self.root
        if node is self.NIL or node is None:
            return []
        return self.in_order(node.left) + [node.key] + self.in_order(node.right)
 
    def black_height(self, node: Optional[RBNode] = None) -> Optional[int]:
        """Return black-height of subtree, or None if invariants violated.
 
        Used as a self-check that insertions left the tree well-formed.
        """
        if node is None:
            node = self.root
        if node is self.NIL or node is None:
            return 1   # NIL counts as black, contributing 1 to the path
        if node.color == RED:
            if (node.left is not None and node.left.color == RED) or \
               (node.right is not None and node.right.color == RED):
                return None  # invariant 4 violated
        lh = self.black_height(node.left)
        rh = self.black_height(node.right)
        if lh is None or rh is None or lh != rh:
            return None
        return lh + (1 if node.color == BLACK else 0)
 
 
# Worked example from §3:
rb = RedBlackTree()
for k in [10, 20, 30, 15, 25, 5, 35, 18]:
    rb.insert(k)
 
assert rb.in_order() == [5, 10, 15, 18, 20, 25, 30, 35]
assert rb.black_height() is not None       # all five invariants hold
assert rb.root.color == BLACK              # invariant 2
 
# Sequential 1..1000 — would degenerate in plain BST, balanced in RB.
rb2 = RedBlackTree()
for k in range(1, 1001):
    rb2.insert(k)
assert rb2.in_order() == list(range(1, 1001))
assert rb2.black_height() is not None

The implementation has two non-obvious design choices worth flagging:

1. The NIL sentinel. Using a single shared NIL leaf (instead of None) means we can read NIL.color without null-checks. CLRS uses this technique throughout. The trade-off is one extra object allocation; the simplification of the fix-up cases is dramatic.

2. Parent pointers. Pure functional or immutable RB trees can be implemented without parent pointers (the recursion stack tracks parents implicitly), but iterative fix-up — which is what production code uses — needs explicit parents. The Linux kernel’s rb_node has a parent pointer with the color packed into its low bit (since pointers are word-aligned).

6. Complexity

6.1 Height bound

Claim: a red-black tree with n internal nodes has height h ≤ 2 · log₂(n + 1).

Proof: Let bh = bh(root) be the tree’s black-height.

• By invariant 5, every path from root to a leaf has exactly bh black nodes.
• By invariant 4, no two reds are adjacent. So in a path of length h, at least ⌈h/2⌉ nodes are black, giving bh ≥ ⌈h/2⌉, equivalently h ≤ 2·bh.
• A subtree rooted at any node v with black-height bh(v) contains at least 2^{bh(v)} − 1 internal nodes. (Inductive proof: a subtree of black-height 0 has at least 2^0 − 1 = 0 internal nodes (it’s NIL); a subtree of black-height bh has two children whose black-heights are bh or bh − 1, contributing at least 2 · (2^{bh−1} − 1) + 1 = 2^bh − 1 total.)
• So n ≥ 2^bh − 1, giving bh ≤ log₂(n + 1).
• Combining: h ≤ 2·bh ≤ 2·log₂(n + 1). ∎

So search, insert, and delete are all O(log n) worst-case.

6.2 Constants compared to AVL

Tree	Height bound	Insert rotations (max)	Delete rotations (max)
AVL Tree	~1.44 · log₂(n + 2)	2	O(log n) cascade
Red-Black	2 · log₂(n + 1)	2	3

AVL: shorter trees, more rebalancing on delete.
Red-Black: ~40% taller worst case, fewer rebalancing rotations on delete.

For typical workloads, the constants in the rotations + recolorings dominate. RB’s bounded-rotation property is what makes it the production default — its worst-case modification cost is more predictable than AVL’s.

6.3 Recoloring vs rotation costs

Insert and delete both do at most O(1) rotations + O(log n) recolorings (the Case 1 climb in insert, Case 2 climb in delete). Recolorings are cheap (one bit flip), so the amortized per-operation cost is dominated by the descent (O(log n)) regardless. The constants matter primarily for cache behavior: each rotation touches 3-5 nodes; each recoloring touches 1.

6.4 Space

Each node stores: key, two child pointers, one parent pointer, and one color bit. The Linux kernel’s rb_node packs the color into the parent pointer’s low bit to avoid the per-node padding cost.

Total: O(n) with a constant of roughly 32 bytes per node on a 64-bit platform, vs ~36 for an AVL tree (the height field doesn’t pack).

7. Production Use — Where RB Trees Actually Live

7.1 Java’s TreeMap and TreeSet

java.util.TreeMap is a textbook RB tree with the standard CLRS five invariants; its implementation (the class itself, in the java.util package) carries comments explicitly crediting CLRS, and it supports O(log n) put/get/remove/firstKey/lastKey/subMap. TreeSet is a thin wrapper around TreeMap. Separately, since Java 8 java.util.HashMap also uses red-black trees: when a single hash bucket accumulates too many colliding entries (treeify threshold 8), that bucket’s linked list is converted into a red-black tree so a pathological or adversarial hash collision degrades lookups to O(log n) instead of O(n) (Red–black tree, Wikipedia).

7.2 C++ STL: std::map, std::set, std::multimap, std::multiset

The standard requires “logarithmic” operations and ordered iteration. libstdc++ and libc++ both implement these as RB trees. std::map<K, V>::insert is O(log n), and the iterator order is the BST in-order traversal.

7.3 Linux kernel

The kernel uses RB trees pervasively, exposed via <linux/rbtree.h>:

• Completely Fair Scheduler (CFS): each runqueue is an RB tree of tasks ordered by virtual runtime; pick-next is O(log n) leftmost-node lookup.
• epoll: the registered file descriptors are stored in an RB tree.
• Memory-management VMA (Virtual Memory Area) tree: each process’s address space is an RB tree of VMAs ordered by start address.
• /proc filesystem nodes, deadline-scheduler, anticipatory IO scheduler — many subsystems use the kernel’s rb_tree.

The kernel’s choice of RB over AVL was driven by the bounded-rotation count (predictable worst-case latency) and the small per-node overhead (parent pointer + color bit packed together).

7.4 Database indexes

PostgreSQL, MySQL InnoDB, and SQLite use B-tree indexes for disk-resident data, not RB trees. The reason: B-trees pack many keys per node, matching the disk page size (4–16 KB) — a single I/O fetches dozens of keys instead of one. RB trees are for in-memory ordered maps; B-trees are for disk-backed indexes. The two are mathematically related (RB ≡ 2-3-4 B-tree binary encoding) but optimized for different storage hierarchies.

7.5 Where AVL is preferred

Some database systems (e.g., older SQLite versions for in-memory tables) use AVL because reads dominate the workload. Some embedded RTOS schedulers prefer AVL for the same reason. In practice, the choice between AVL and RB is rarely a bottleneck; pick whichever your standard library provides.

8. Pitfalls

8.1 Forgetting to root-color-flip

After every _insert_fixup, the root must be black (invariant 2). Forgetting self.root.color = BLACK at the end means future inserts may see a red root and incorrectly trigger Case 1 violations. This bug is silent on small trees (a quick print shows red roots all over the place) and corrupts later operations.

8.2 NIL sentinel vs None

Mixing the two is the most common implementation bug. CLRS uses a shared NIL sentinel; some implementations use None. The fix-up cases reference parent.color and uncle.color — if any of those is None, you get a NullPointerException. The fix is uniformity: choose one and use it everywhere, including in the rotations.

8.3 Parent pointer not updated on rotation

_rotate_left(x) must update x.right.parent (which becomes x’s grandparent’s child) AND x.parent (which becomes y). Forgetting either leaves dangling parents — and the iterative fix-up walks z.parent until hitting a black ancestor, so wrong parent pointers cause infinite loops.

8.4 Confusing left-leaning and standard RB trees

Sedgewick’s “left-leaning red-black trees” (LLRB, 2008) are a different simplification with only ~6 cases instead of CLRS’s ~12 (counting symmetric mirrors). They enforce the additional invariant “no right-leaning red links,” which forces every red link to lean left. Implementations are shorter; performance is similar. Production code generally uses CLRS-style RB, not LLRB. Don’t mix conventions; the case structure differs.

8.5 Forgetting symmetric cases

Insert fix-up has six cases (1, 2, 3 + their mirrors when parent is the right child of grandparent). Coding only the “left side” works for half the inserts and silently mangles the other half. The pseudocode in §4.2 is half-shown for brevity; production code must include both branches.

8.6 Off-by-one in black-height counting

Whether NIL counts toward the black-height (CLRS) or not (some textbooks). With NIL counting, the leaves’ black-height is 1; without, it’s 0. The proofs come out the same — just shifted by 1 — but mixing the conventions in a single proof breaks the math.

8.7 Using RB when a Skip List suffices

Skip Lists are simpler to implement (~30 lines vs ~150 for RB), give expected O(log n) performance, and don’t have rotation cases at all. For most “I need an ordered map” use cases without strict worst-case guarantees, skip lists are the friendlier choice. RB’s win is the deterministic worst case.

8.8 Blowing up the recursion

Recursive RB code in Python should be fine (height ≤ 2·log₂ n ≈ 64 for n = 4·10⁹), but iterative implementations are standard in production for predictable stack usage.

8.9 Parent-pointer confusion during deletion

Delete is structurally complicated by the case where the spliced node has a child that needs to take its place. Updating child.parent and the parent.left/parent.right link to child is error-prone. The CLRS pseudocode uses an RB-Transplant helper for this; recreating it freely from memory is a common interview trip-up.

9. Diagrams — The Three Insert Fix-Up Cases

9.1 Case 1 — Uncle is red (recolor)

Before (z is the new red leaf, parent and uncle both red):

           G·B
          /    \
        P·R    U·R
        /
       z·R

After recolor (parent + uncle → black, grandparent → red):

           G·R          ← may now have a red parent itself; recurse upward
          /    \
        P·B    U·B
        /
       z·R                ← no longer in violation

What this diagram shows. When both parent and uncle are red, the local fix is a recoloring: flip parent and uncle to black (eliminating the red-red violation at z) and flip the grandparent to red (preserving the black-height invariant — every path through the grandparent loses one black at the parent/uncle level and gains one at the grandparent level). The trade-off: we may have just created a red-red violation between the grandparent and its parent. The fix-up loop continues at the grandparent. Each iteration of the loop climbs 2 levels, so it terminates in O(log n) steps. No rotations performed in this case.

9.2 Case 2 — Uncle is black, z is on the inner side (zigzag)

Before:

           G·B
          /    \
        P·R    U·B
          \
           z·R

After left-rotate at P (transforms zigzag into straight line):

           G·B
          /    \
        z·R    U·B
        /
       P·R

This is now Case 3.

What this diagram shows. When the uncle is black and z is the inner grandchild (right child of left child, or vice versa), a single rotation at the grandparent would just produce the mirror-image violation. We first straighten the zigzag with a rotation at the parent — z and P swap roles. Now the new z (which was P) is on the outer side, reducing to Case 3. No recolorings yet — those come in Case 3.

9.3 Case 3 — Uncle is black, z is on the outer side (straight line)

Before:

           G·B
          /    \
        P·R    U·B
        /
       z·R

After right-rotate at G + recolor (P → black, G → red):

           P·B          ← was red, now black
          /    \
        z·R    G·R       ← was black, now red
                  \
                  U·B

What this diagram shows. With a black uncle and z on the outer side, we rotate at the grandparent (turning P into the new subtree root) and swap P and G’s colors. The result has no red-red violation (P is now black, both its children are red but each red has black children). The black-height is preserved because: the previous “G·B – U·B” path had 1 black before NIL; the new “P·B – G·R – U·B” path also has 2 blacks (one at P, one at U). The new “P·B – z·R” path has 1 black at P, and any subtree under z has the same blacks as before. ✓

The fix-up terminates after Case 3 — no further violations can exist above. So Case 3 (and its mirror) does at most one rotation per insert.

9.4 Combined insert behavior

A typical insert sequence:

1. Cases 1 (red uncle): zero or more recolorings climbing the tree — O(log n) total.
2. End in Case 2 + 3 (black uncle): zero or one rotations to fix the final violation.
3. Root recolor to black.

Total: at most 2 rotations, O(log n) recolorings.

10. Common Interview Problems

LC# / Source	Problem	Use of RB
LC 220	Contains Duplicate III	Sliding-window + sorted set queries. C++ STL multiset is RB.
LC 729	My Calendar I	Interval ordered set — backed by RB in many languages.
LC 218	The Skyline Problem	Sweep line + sorted multiset of heights — std::multiset/TreeMap is the canonical solution.
LC 315	Count of Smaller Numbers After Self	Order-statistic tree — augmented RB or BIT.
LC 327	Count of Range Sum	Sorted prefix-sum lookup — TreeSet-style.
LC 855	Exam Room	Sorted set of seated students — RB-backed.
LC 480	Sliding Window Median	Two heaps or balanced BST. RB allows direct k-th lookup with augmentation.
Java/C++	“Implement TreeMap”	Standard library function is RB; some interviews ask to recreate the API.

For the interview itself, knowing RB’s five invariants and its production-ubiquity is more important than implementing fix-up cases live. Most interviewers will ask “what’s a red-black tree?”, “what are the invariants?”, “why prefer it over AVL?”, “where is it used?” — answering these earns most of the points.

11. Open Questions

• Why didn’t AVL win the production default war? Anecdotally it’s “fewer rotations on delete,” but quantitatively the gap is small. Some posit that Bayer’s earlier B-tree connection made RB easier to teach.
• Does Sedgewick’s left-leaning RB save enough implementation complexity to be worth the slight performance loss? Production C++ STL hasn’t switched.
• How does WAVL (weak AVL, Haeupler-Sen-Tarjan 2015) compare? It’s a recent result that supposedly combines AVL’s height bound with RB’s bounded-rotation count. I haven’t seen it adopted in production.

11.1 A note on the naming history

The lineage is well established. The data structure was invented by Rudolf Bayer in 1972 under the name symmetric binary B-trees, as a binary encoding of B-trees. The colors — and the name “red-black” — were introduced by Leonidas Guibas and Robert Sedgewick in their 1978 FOCS paper “A dichromatic framework for balanced trees,” which derived the structure directly from Bayer’s symmetric binary B-trees (A dichromatic framework for balanced trees, Guibas & Sedgewick 1978; see also the Red–black tree, Wikipedia summary). The often-repeated trivia about why red and black were chosen is unsettled even among the inventors: one account holds the colors rendered best on the Xerox PARC color laser printer the authors used; Guibas has separately said they simply had red and black pens for drawing the trees. The two-color choice itself, however, is not in doubt, and the algorithm is unambiguous regardless.

12. See Also

• AVL Tree — the strict-balance sibling; same O(log n) bounds, different constants
• Binary Search Tree — the unbalanced ancestor
• B-Tree — RB is a binary encoding of 2-3-4 B-trees
• Tree Traversals — in-order traversal of any RB is sorted
• Binary Tree
• Hash Table — alternative when ordering isn’t needed
• Skip List — randomized alternative with similar bounds, simpler code
• Big-O Notation
• SWE Interview Preparation MOC