Red-Black Tree
Visualize self-balancing binary search trees through nodes and recoloring.
Free theory articleVisualize 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:
- Set Nodes to Insert to
12and Animation Speed to1000ms, then press Play. - Observe the first key enter as the root node colored dark zinc (Black) while its immediate children enter colored crimson (Red).
- 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.
- 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.