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:
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:
- Insert 10: Inserted as Red root, then immediately recolored Black by Property 2:
10(B). - Insert 20: Attached as the Red right child of
10(B). Since parent10(B)is Black, all five properties hold without fixup. - 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 grandparent10(B)and swapping colors of10and20promotes20(B)to the root with two Red children10(R)and30(R). - Insert 15 (Red uncle → recoloring): Attached as the Red right child of
10(R). Because both parent10(R)and uncle30(R)are Red, Case 1 recolors10and30to Black, flips grandparent20to Red, and finally restores root20(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:
- 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.
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:
- Guibas, L. J., & Sedgewick, R. (1978). A Dichromatic Framework for Balanced Trees. 19th Annual Symposium on Foundations of Computer Science (FOCS), 8–21.
- Morin, P. Open Data Structures, Section 9.2: RedBlackTree.
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 →