Red-Black Tree

Rudolf Bayer, 1972

Red-Black trees maintain balance by coloring each node red or black and enforcing properties: the root is black, red nodes have black children, and all paths from root to null leaves have the same black-height. After insertion, color flips and rotations restore these invariants. The visualization shows red nodes in coral and black nodes in dark gray, with a gold ring on the node being inserted or fixed.