RB trees, almost balanced (Bayer, 1972)

Nodes are either red or black
Children of red nodes must be black
All root-to-leaf paths have the same number of black nodes


      Image: Colin M.L. Burnett (Cburnett), CC-BY-SA-3.0-unported