Computer Science

Red-Black Tree

Visualize self-balancing binary search trees through nodes and recoloring.

By Riano · Published · Updated · Report a correction

Red-Black Tree

Concept Overview

A Red-Black tree is a self-balancing binary search tree that stores one color bit (red or black) per node to encode a 2-3-4 B-Tree as a binary tree. By forbidding two consecutive red nodes on any root-to-leaf path while requiring every root-to-NIL path to contain the exact same number of black nodes (the black-height), a Red-Black tree guarantees that no leaf is more than twice as deep as any other leaf and bounds height to 2 log2(n + 1).

Mathematical Definition

Every Red-Black tree satisfies five invariants:

1. Every node is colored either Red or Black.
2. The root node is Black.
3. Every NIL leaf sentinel is Black.
4. Red rule: If a node is Red, both of its children are Black.
5. Black-height rule: Every simple path from a node x to a descendant NIL leaf contains the same number of Black nodes, bh(x).

Height bound for n internal nodes: h ≤ 2 log2(n + 1)

Worked Example: Uncle Recoloring vs. Rotation During Insertion

Every newly inserted key starts colored Red so the black-height invariant (Property 5) is preserved automatically; only the Red rule (Property 4) or root rule (Property 2) can be violated. Trace inserting 10, 20, 30, 15:

  1. Insert 10: Inserted as Red root, then immediately recolored Black by Property 2: 10(B).
  2. Insert 20: Attached as the Red right child of 10(B). Since parent 10(B) is Black, all five properties hold without fixup.
  3. Insert 30 (Black uncle → rotation): Attached as the Red right child of 20(R), creating a Red-Red violation (20(R) → 30(R)) with a Black (NIL) uncle. Left-rotating around grandparent 10(B) and swapping colors of 10 and 20 promotes 20(B) to the root with two Red children 10(R) and 30(R).
  4. Insert 15 (Red uncle → recoloring): Attached as the Red right child of 10(R). Because both parent 10(R) and uncle 30(R) are Red, Case 1 recolors 10 and 30 to Black, flips grandparent 20 to Red, and finally restores root 20(B) to Black—increasing the tree's black-height by 1 with zero rotations.

Interactive Experiment: What to Enter and Observe

Open the Red-Black Tree module to observe how color flips and rotations maintain the black-height and red-parent invariants:

  1. Set Nodes to Insert to 12 and Animation Speed to 1000ms, then press Play.
  2. Observe the first key enter as the root node colored dark zinc (Black) while its immediate children enter colored crimson (Red).
  3. Press Pause after several insertions and verify two visual invariants across the entire canvas: (a) no crimson Red node ever has a crimson Red child, and (b) every root-to-leaf path passes through the exact same number of dark Black nodes.
  4. Click the Reset tree button, increase Nodes to Insert to 25, and press Play to see how Red-Black rebalancing keeps the tree wide and shallow even as 25 keys are inserted.

Assumptions & Trade-offs

Every Red-Black insertion fixup terminates after at most 2 rotations (and at most 3 rotations for deletion), even though recoloring can propagate O(log n) levels up the tree. This O(1) rotation bound per update makes Red-Black trees preferred over AVL trees for persistent data structures and standard library containers (such as C++ std::map and Java TreeMap), at the cost of allowing a path with alternating Red and Black nodes to be up to twice as long as an all-Black path.

References

Guibas and Sedgewick formalized the Red-Black correspondence with 2-3-4 B-Trees in 1978, and Open Data Structures Chapter 9 provides a complete analysis of Red-Black insertion and black-height invariants:

Experience it interactively

Adjust parameters, observe in real time, and build deep intuition with Riano’s interactive Red-Black Tree module.

Try Red-Black Tree on Riano →

More in Computer Science