Red-Black Tree
Self-Balancing BSTO(log n)height = 4A self-balancing BST where each node carries a color bit (Red or Black). Five invariants guarantee O(log n) height. Violations are fixed via recoloring and rotations.
Use the controls below to insert, search, or delete nodes.
RB Invariants
✓Root is Black
✓No consecutive Reds
✓Black heights consistent
Legend
Red node
Black node
Highlighted
Highlighted edge
Operation Log
Demo: inserted [10, 20, 30, 15, 25, 5, 1, 7, 35, 40]
Insert fix-up cases
Case 1 — Uncle Red
Parent & uncle both Red
Recolor parent + uncle Black, grandparent Red. Move z up.
Case 2 — Uncle Black, zig-zag
LR or RL shape with uncle Black
Rotate parent to straighten → becomes Case 3.
Case 3 — Uncle Black, straight
LL or RR shape with uncle Black
Rotate grandparent + swap colors of parent & grandparent.
The 5 Red-Black invariants
1.Every node is Red or Black.
2.The root is Black.
3.Every nil leaf is Black.
4.If a node is Red, both children are Black.
5.All paths root→nil have equal Black-node count.