Part 06•Chapter 5 of 10•Intermediate

Red-Black Trees (RBT)

The 5 fundamental RBT invariants, black-height mathematical proof, 3-case insertion recoloring/rotations, and 4-case deletion handling.

~15 min read

2,826 words

19 Sections

Reviewed & Verified (2024 Syllabus)

Keys: [ Prev • ] Next

5 Red-Black InvariantsBlack-Height Invariant ProofUncle Node Color Cases

Red-Black Trees relax the rigid geometric balance of AVL trees by encoding structural balance into node color bits, bounding maximum height to $2 lo g_{2} (n + 1)$ . This compromise guarantees logarithmic searches while constraining worst-case insertion rebalancing to at most two rotations and deletion rebalancing to at most three.

1. Executive Summary & Learning Objectives

Invented by Rudolf Bayer in 1972 as Symmetric Binary B-Trees and formalized by Leo Guibas and Robert Sedgewick in 1978, a Red-Black Tree is a self-balancing binary search tree that uses one additional bit of storage per node—its color (RED or BLACK)—to ensure that no simple path from the root to a leaf is more than twice as long as any other.

By the end of this chapter, you will be able to:

Formulate the five foundational Red-Black Tree invariants and compute the black-height $bh (u)$ of any arbitrary node.
Reproduce the inductive proof demonstrating that a red-black tree with $n$ internal nodes has height $h \leq 2 lo g_{2} (n + 1)$ .
Execute the three canonical insertion fixup cases, correctly distinguishing recoloring operations from parent-rotation and grandparent-rotation rebalancing.
Dissect the four double-black deletion fixup cases and trace how extra blackness is absorbed or rotated out.
Evaluate trade-offs between Red-Black trees and AVL trees for read-heavy versus write-heavy systems (e.g., Linux CFS scheduler, C++ std::map).

2. The 5 Structural Red-Black Tree Invariants

Every valid Red-Black Tree must strictly satisfy all five properties at all times:

Invariant Number	Invariant Name	Formal Specification	Architectural Purpose
1	Node Color Property	Every node $u \in T$ is colored either `RED` or `BLACK`.	Binary classification used to maintain balance.
2	Root Property	The root node is always `BLACK`.	Serves as an invariant baseline for black-height.
3	Leaf Property	Every external leaf (`NIL` sentinel node) is `BLACK`.	Standardizes path termination with zero black-height contribution.
4	Red Property	If a node is `RED`, both of its children must be `BLACK`.	Prohibits consecutive `RED` nodes; bounds path length variance.
5	Black-Height Property	For every node $u$ , all simple paths from $u$ to descendant leaves contain the exact same number of `BLACK` nodes ( $bh (u)$ ).	Enforces global structural balance across all subtrees.

⚙️

Canonical Red-Black Tree Layout

The table below illustrates a valid Red-Black Tree containing keys ${5, 10, 15, 20, 30, 40}$ with black-height $bh (root) = 2$ :

Key	Node Color	Parent	Left Child	Right Child	Black-Height $bh$	Verification Path to Leaves
20	`BLACK`	`null`	`10`	`30`	$2$	Root node (Black-Height baseline: 2)
10	`RED`	`20`	`5`	`15`	$1$	Left child of root (Children must be Black)
30	`BLACK`	`20`	`NIL`	`40`	$1$	Right child of root
5	`BLACK`	`10`	`NIL`	`NIL`	$1$	Leaf child (Path to NIL: 1 black node)
15	`BLACK`	`10`	`NIL`	`NIL`	$1$	Leaf child (Path to NIL: 1 black node)
40	`RED`	`30`	`NIL`	`NIL`	$0$	Leaf child (Path to NIL: 0 additional black nodes)

Path Verification:

Path $20 \to 10 \to 5 \to NIL$ : Black nodes = ${20, 5}$ (Count = 2).
Path $20 \to 10 \to 15 \to NIL$ : Black nodes = ${20, 15}$ (Count = 2).
Path $20 \to 30 \to NIL$ : Black nodes = ${20, 30}$ (Count = 2).
Path $20 \to 30 \to 40 \to NIL$ : Black nodes = ${20, 30}$ (Count = 2). All paths encounter exactly 2 black nodes! Invariant 5 is globally satisfied.

3. Mathematical Proof of Height Bound $h \leq 2 lo g_{2} (n + 1)$

Theorem

A Red-Black Tree with $n$ internal nodes has height at most:

h \leq 2 lo g_{2} (n + 1)

Formal Proof in Three Steps

Step 1: Subtree Size Lemma

Claim: The subtree rooted at any node $x$ contains at least $2^{bh (x)} - 1$ internal nodes.

Proof by Structural Induction on the height of $x$ :

Base Case: If height $h (x) = 0$ , $x$ is an external sentinel leaf (NIL). Its black-height is $bh (x) = 0$ , and internal nodes $= 2^{0} - 1 = 0$ . The base case holds.
Inductive Step: Consider an internal node $x$ with height $h (x) > 0$ and two children $c_{1}, c_{2}$ .
- If child $c_{i}$ is RED, $bh (c_{i}) = bh (x)$ (since the child's red color does not augment black-height).
- If child $c_{i}$ is BLACK, $bh (c_{i}) = bh (x) - 1$ .
- Therefore, in both scenarios: $bh (c_{i}) \geq bh (x) - 1$ .
- By inductive hypothesis, each child's subtree contains at least $2^{bh (x) - 1} - 1$ internal nodes.
- Summing the subtrees and counting internal node $x$ itself:

Internal Nodes (x) \geq 1 + (2^{bh (x) - 1} - 1) + (2^{bh (x) - 1} - 1) = 2 \cdot 2^{bh (x) - 1} - 1 = 2^{bh (x)} - 1

The lemma is proven for all internal nodes. $■$

Step 2: Linking Black-Height to Tree Height

According to Invariant 4 (Red Property), no two RED nodes can appear consecutively on any simple path from the root to a leaf. Therefore, on any simple path from the root to a leaf, at least half of the nodes (excluding the root itself) must be BLACK. Consequently:

bh (root) \geq \frac{h}{2}

Step 3: Combining the Inequalities

Let $n$ be the number of internal nodes in the entire tree:

n \geq 2^{bh (root)} - 1 \geq 2^{h /2} - 1

n + 1 \geq 2^{h /2}

Taking the base-2 logarithm of both sides:

lo g_{2} (n + 1) \geq \frac{h}{2} ⟹ h \leq 2 lo g_{2} (n + 1)

∴ Search, Insertion, and Deletion are strictly bounded to Θ (lo g n) worst-case! ■

4. Insertion Mechanics & The 3 Uncle Fixup Cases

Insertion Strategy

Perform standard Binary Search Tree insertion to insert the new node $z$ at a leaf position.
Color the new node $z$ RED:
- Coloring $z$ RED preserves Invariant 5 (Black-Height) across all paths.
- If $z$ is the root, recolor it BLACK to satisfy Invariant 2.
- If $z$ 's parent is BLACK, all invariants hold; the algorithm terminates immediately.
If $z$ 's parent $p$ is RED, Invariant 4 is violated (Double Red). We invoke InsertFixup(z).

The 3 Canonical Uncle Cases (Parent is Left Child of Grandparent)

Let $z$ be the newly inserted node, $p$ its parent, $g$ its grandparent, and $y$ its uncle (sibling of $p$ , i.e., $g . right$ ):

Case	Geometric Condition	Uncle Color	Surgical Action	Post-Action Status
Case 1: Red Uncle	$z$ 's uncle $y$ is `RED`	`RED`	Color Flip: Recolor parent $p \leftarrow BLACK$ , uncle $y \leftarrow BLACK$ , grandparent $g \leftarrow RED$ .	Advance $z \leftarrow g$ ; repeat loop upward.
Case 2: Triangle (Inside Child)	$z$ 's uncle $y$ is `BLACK`, $z$ is a right child ( $z = p . right$ )	`BLACK`	Rotate Parent: Perform `LeftRotate(p)`. Advance $z \leftarrow p$ .	Transforms immediately into a straight line (Case 3).
Case 3: Line (Outside Child)	$z$ 's uncle $y$ is `BLACK`, $z$ is a left child ( $z = p . left$ )	`BLACK`	Rotate Grandparent & Swap Colors: Recolor $p \leftarrow BLACK$ , $g \leftarrow RED$ . Perform `RightRotate(g)`.	All invariants satisfied; TERMINATE.

Step-by-Step Structural Transformation Matrix

The table below illustrates the pointer and color mutations across the 3 insertion fixup cases:

Case	Configuration Before Fixup	Primary Transformation	Configuration After Fixup
Case 1: Color Flip	Grandparent $g (B)$ has two red children $p (R)$ and $y (R)$ . Node $z (R)$ is child of $p$ .	Recolor $p \to B$ , $y \to B$ , $g \to R$ .	Grandparent $g (R)$ becomes the active node $z$ . No rotations needed. Invariant 5 preserved.
Case 2: Triangle to Line	Grandparent $g (B)$ , parent $p (R)$ (left child of $g$ ), node $z (R)$ (right child of $p$ ), uncle $y (B)$ .	Execute `LeftRotate(p)`.	Node $z$ becomes parent of $p$ . Both are in a straight left-child line beneath $g$ .
Case 3: Line Rotation	Grandparent $g (B)$ , parent $p (R)$ (left child of $g$ ), node $z (R)$ (left child of $p$ ), uncle $y (B)$ .	Recolor $p \to B$ , $g \to R$ . Execute `RightRotate(g)`.	Node $p (B)$ becomes subtree root with left child $z (R)$ and right child $g (R)$ . Fully balanced!

(Note: If parent $p$ is the right child of grandparent $g$ , symmetric mirror cases apply with Left and Right swapped).

5. Complete Implementation: Insertion Fixup

typescript

export enum Color {
  RED,
  BLACK,
}

export class RBNode<T> {
  key: T;
  color: Color = Color.RED;
  left: RBNode<T> | null = null;
  right: RBNode<T> | null = null;
  parent: RBNode<T> | null = null;

  constructor(key: T) {
    this.key = key;
  }
}

export class RedBlackTree<T> {
  root: RBNode<T> | null = null;

  private leftRotate(x: RBNode<T>): void {
    const y = x.right!;
    x.right = y.left;
    if (y.left !== null) y.left.parent = x;

    y.parent = x.parent;
    if (x.parent === null) {
      this.root = y;
    } else if (x === x.parent.left) {
      x.parent.left = y;
    } else {
      x.parent.right = y;
    }

    y.left = x;
    x.parent = y;
  }

  private rightRotate(y: RBNode<T>): void {
    const x = y.left!;
    y.left = x.right;
    if (x.right !== null) x.right.parent = y;

    x.parent = y.parent;
    if (y.parent === null) {
      this.root = x;
    } else if (y === y.parent.left) {
      y.parent.left = x;
    } else {
      y.parent.right = x;
    }

    x.right = y;
    y.parent = x;
  }

  public insert(key: T): void {
    const z = new RBNode(key);
    let y: RBNode<T> | null = null;
    let x = this.root;

    while (x !== null) {
      y = x;
      if (z.key < x.key) {
        x = x.left;
      } else if (z.key > x.key) {
        x = x.right;
      } else {
        return; // Duplicate key: ignore
      }
    }

    z.parent = y;
    if (y === null) {
      this.root = z;
    } else if (z.key < y.key) {
      y.left = z;
    } else {
      y.right = z;
    }

    z.color = Color.RED;
    this.insertFixup(z);
  }

  private insertFixup(z: RBNode<T>): void {
    while (z.parent !== null && z.parent.color === Color.RED) {
      if (z.parent === z.parent.parent?.left) {
        const uncle = z.parent.parent.right;

        // CASE 1: Uncle is RED -> Color Flip
        if (uncle !== null && uncle.color === Color.RED) {
          z.parent.color = Color.BLACK;
          uncle.color = Color.BLACK;
          z.parent.parent.color = Color.RED;
          z = z.parent.parent;
        } else {
          // CASE 2: Uncle is BLACK & z is Right child -> Rotate Parent
          if (z === z.parent.right) {
            z = z.parent;
            this.leftRotate(z);
          }

          // CASE 3: Uncle is BLACK & z is Left child -> Rotate Grandparent & Recolor
          z.parent!.color = Color.BLACK;
          z.parent!.parent!.color = Color.RED;
          this.rightRotate(z.parent!.parent!);
        }
      } else {
        // Symmetric mirror cases
        const uncle = z.parent.parent?.left ?? null;

        if (uncle !== null && uncle.color === Color.RED) {
          z.parent.color = Color.BLACK;
          uncle.color = Color.BLACK;
          z.parent.parent!.color = Color.RED;
          z = z.parent.parent!;
        } else {
          if (z === z.parent.left) {
            z = z.parent;
            this.rightRotate(z);
          }

          z.parent!.color = Color.BLACK;
          z.parent!.parent!.color = Color.RED;
          this.leftRotate(z.parent!.parent!);
        }
      }
    }

    this.root!.color = Color.BLACK;
  }
}

6. Step-by-Step Dry Run State Trace Table

Consider sequentially inserting keys $[10, 20, 30, 15]$ into an initially empty Red-Black Tree.

Step	Operation	Active Node $z$	Tree State Before Fixup	Triggered Condition	Fixup Actions Performed	Final Subtree Colors
1	Insert $10$	$10$	Single node $10 (R)$	$10$ is root	Invariant 2 enforcement: recolor root $10 \to BLACK$ .	$10 (B)$
2	Insert $20$	$20$	$10 (B) \to right (20 (R))$	Parent is `BLACK`	No violation! Invariants hold immediately.	$10 (B), 20 (R)$
3	Insert $30$	$30$	$10 (B) \to right (20 (R)) \to right (30 (R))$	Parent $20 (R)$ is `RED`, Uncle is `NIL` (`BLACK`)	Case 3 (Mirror): Recolor $20 \to B, 10 \to R$ . Left-Rotate around grandparent $10$ .	$20 (B)$ (new root), $10 (R)$ , $30 (R)$
4	Insert $15$	$15$	Attaches as right child of $10 (R)$	Double Red ( $10 (R)$ and $15 (R)$ ). Uncle $30 (R)$ is `RED`!	Case 1: Color Flip: Recolor $10 \to B, 30 \to B, 20 \to R$ . Root $20$ recolored `BLACK`.	$20 (B)$ (root), $10 (B), 30 (B), 15 (R)$

7. Deletion Mechanics & The 4 Double-Black Fixup Cases

When deleting an internal node $v$ , it is replaced by its successor $s$ . Splicing out node $y$ with replacement child $x$ reduces the case to removing a node with at most one child:

If $y$ was RED: No black-height property is violated. All invariants remain valid!
If $y$ was BLACK: The path passing through $x$ is now short by 1 black node. We conceptually assign an extra unit of blackness to $x$ , making $x$ Double-Black.

Let $x$ be the Double-Black node, $p$ its parent, and $w$ its sibling:

Case	Condition at Sibling $w$	Rebalancing Action	Outcome / Transformation
Case 1	Sibling $w$ is `RED`	Left-rotate parent $p$ . Recolor $p \leftarrow RED$ , $w \leftarrow BLACK$ .	Converts to Case 2, 3, or 4 where sibling is `BLACK`.
Case 2	Sibling $w$ is `BLACK`, and both of $w$ 's children are `BLACK`	Recolor $w \leftarrow RED$ . Absorb extra black into parent $p$ .	Parent $p$ becomes Double-Black. Advance $x \leftarrow p$ and propagate upward.
Case 3	Sibling $w$ is `BLACK`, inner child is `RED`, outer child is `BLACK`	Right-rotate sibling $w$ away from inner child. Swap colors of $w$ and inner child.	Transforms immediately into Case 4 with an outer `RED` child.
Case 4	Sibling $w$ is `BLACK`, outer child is `RED`	Left-rotate parent $p$ . Sibling $w$ takes $p$ 's color; recolor $p$ and outer child `BLACK`.	Double-black is completely eliminated! Algorithm terminates.

8. Red-Black Tree vs. AVL Tree Trade-Off Matrix

Metric / Dimension	AVL Tree	Red-Black Tree
Balance Invariant	$∣ B F (u) ∣ \leq 1$	$Path_{m a x} \leq 2 \times Path_{m i n}$
Strict Height Bound	$\leq 1.44 lo g_{2} n$	$\leq 2.00 lo g_{2} n$
Lookup Speed	$\approx 15 - 20%$ faster (due to shallower tree)	Slightly slower (longer search paths)
Insertion Rotations	$\leq 2$ rotations	$\leq 2$ rotations
Deletion Rotations	$O (lo g n)$ rotations (can cascade to root)	$\leq 3$ rotations strictly guaranteed
Memory Overhead	2 bits (balance factor) or 1 integer	1 bit (color: `RED`/`BLACK`)
Primary Industry Adoption	Search-heavy index systems, static dictionaries	Linux kernel (`rbtree.c`), C++ `std::map`, Java `TreeMap`

9. Common Traps, Edge Cases & Implementation Pitfalls

Failure to Recolor the Root:
- Color flip propagation (Case 1) can push a RED color all the way to the tree root. The fixup routine must unconditionally reset root.color = BLACK upon loop termination.
Sentinel Node Parent Pointer Corruption:
- In implementations using a shared global NIL sentinel node, mutations to NIL.parent by rotation logic can corrupt subsequent sentinel queries. Using a dedicated sentinel object with immutable null pointers prevents this fault.
Triangle vs. Line Child Identification:
- Incorrectly matching Case 2 instead of Case 3 occurs when testing $z$ 's relationship to its grandparent rather than its parent. Ensure $z === p . right$ is checked against $p === g . left$ .

10. Real-World Applications & Practice Problems

Production Systems

Linux Completely Fair Scheduler (CFS): Linux tracks runnable tasks ordered by virtual runtime (vruntime) using an augmented Red-Black tree (linux/rbtree.h), enabling $O (1)$ selection of the minimum runtime process.
Memory Allocators (jemalloc): Uses Red-Black trees to track free memory chunks indexed by address and size for rapid buddy-allocation coalescing.

Standard Practice Problems

Red-Black Tree Insertion Fixup — Implement insertFixup with full uncle classification and rotations.
Double-Black Deletion Fixup — Implement deleteFixup covering all 4 sibling color permutations.

11. References & Academic Attribution

Bayer, R. (1972). Symmetric binary B-Trees: Data structure and maintenance algorithms. Acta Informatica, 1(4), 290–306.
Guibas, L. J., & Sedgewick, R. (1978). A dichromatic framework for balanced trees. 19th Annual Symposium on Foundations of Computer Science (SFCS), 8–21. IEEE.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.), Chapter 13. MIT Press.