Explore modules

Red-Black Tree

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

Free theory article

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

Concept & interpretation

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).

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.
Read the full free theory article