Röd-svart-träd
Självbalanserande binärt sökträd med "färg"-invarianter — Rudolf Bayer 1972, namn av Leonidas Guibas (1978). Vanligaste valet i standardbibliotek.
Fem regler garanterar O(log n) djup utan att balansera lika strikt som AVL. Resultat: snabbare insert/delete än AVL, marginellt långsammare lookup. Operationer kräver rotationer + omfärgningar.
Driver C++ std::map, Java TreeMap/TreeSet, Linux Completely Fair Scheduler, Linux epoll, många nätverk-stack-implementationer. Konkurrent: B-träd (för disk), AVL (lookup-tunga workloads), Skip list (enklare att implementera lock-free).