Podręcznik

Drzewa czerwono-czarne (ang. Red-Black Tree - RBT) to rodzaj zrównoważonych binarnych drzew wyszukiwania (BST), w których stosuje się mechanizmy kolorowania węzłów oraz odpowiednie operacje rotacji w celu utrzymania równowagi struktury. Drzewa RBT zostały stworzone kilkanaście lat później niż drzewa AVL, w latach 1972-78 i od tej pory były coraz coraz powszechniej używane w wielu prężnie rozwijających się dziedzinach informatyki (m.in. w algorytmach geometrii obliczeniowej i gier komputerowych). Każdy węzeł drzewa RBT zawiera dodatkową informację - kolor, który może być albo czerwony, albo czarny. Ten dodatkowy bit informacji w węźle pozwala na wykonywanie operacji równoważenia drzewa, pełni więc tę samą rolę jak wskaźnik wyważenia w drzewie AVL.

Warto dodać, że na ogół nie rysuje się liści drzewa RBT, gdyż wiadomo, że wszystkie liście są czarne i nie wnoszą żadnych istotnych informacji.