Podręcznik

Głównym celem stosowania drzew czerwono-czarnych jest zapewnienie, że wysokość drzewa pozostaje logarytmiczna względem liczby węzłów, co gwarantuje wydajność operacji takich jak wstawianie, usuwanie i wyszukiwanie na poziomie O(log n). Poprzez ustalenie warunków na następstwo kolorów na ścieżkach, gwarantowane jest, że każda ścieżka jest co najwyżej dwukrotnie dłuższa niż dowolna inna ścieżka prowadząca z tego samego wierzchołka. Wynika to z faktu, że najkrótsza możliwa ścieżka zawiera kolejno same węzły czarne, a najdłuższa - czerwone i czarne na przemian. A ponieważ wiemy, że na każdej ścieżce musi być tyle samo węzłów czarnych, to czerwonych może być co najwyżej drugie tyle. Klasyfikuje to drzewa RBT do grupy w przybliżeniu zrównoważonych.

Oryginalna koncepcja drzew czerwono-czarnych doczekała się ważnej modyfikacji przez samego autora, profesora Roberta Sedgewicka z Princeton University. Po 30 latach (!) od swojego pierwotnego pomysłu, w 2008 roku, opracował on zmianę w algorytmie tworzenia drzew, który zakłada pełną jednoznaczność przedstawienia drzewa czerwono-czarnego. Drzewa takie noszą nazwę Left-Leaning Red Black Trees - LLRBT). W klasycznym drzewie czerwono-czarnym czerwone krawędzie (czyli połączenia rodzic–dziecko, w których jedno z tych węzłów jest czerwone) mogą występować zarówno po lewej, jak i prawej stronie. W praktyce jednak taka elastyczność komplikuje implementację, zwłaszcza podczas wstawiania i usuwania elementów, ponieważ trzeba obsługiwać więcej przypadków rotacji i kolorowań.