Rood-zwarte boom
Zelfbalancerende binaire zoekboom met kleurinvarianten — Rudolf Bayer 1972, de naam komt van Leonidas Guibas (1978). De meest gekozen variant in standaardbibliotheken.
Vijf regels garanderen een diepte van O(log n), zonder zo streng te balanceren als AVL. Het resultaat: sneller invoegen en verwijderen dan bij AVL, iets tragere opzoekingen. Bewerkingen vereisen rotaties en herkleuring.
Zit onder C++ std::map, Java TreeMap/TreeSet, de Linux Completely Fair Scheduler, Linux epoll en tal van netwerkstacks. Alternatieven: B-tree (voor schijven), AVL (bij veel opzoekingen) en skip list (eenvoudiger lock-free te implementeren).