🌲 Drzewo czerwono-czarne — samoważące się BST

Rotacja w lewo wokół węzła x sprawia, że prawe dziecko x, y, staje się nowym korzeniem poddrzewa, przesuwając x w dół jako lewe dziecko y i przyjmując dawne lewe poddrzewo y jako nowe prawe dziecko x. Jest stosowana, gdy drzewo ma niezbalansowanie skierowane w prawo — konkretnie podczas wstawiania, gdy nowy czerwony węzeł jest prawym dzieckiem prawego dziecka (przypadek „prawo-prawo” w naprawie po wstawieniu).

Niech bh(x) będzie czarną wysokością węzła x. Zgodnie z zasadą braku kolejnych czerwonych, co najwyżej połowa węzłów na dowolnej ścieżce od korzenia do liścia może być czerwona, więc rzeczywista wysokość h ≤ 2·bh(korzeń). Poddrzewo zakorzenione w dowolnym węźle o czarnej wysokości k zawiera co najmniej 2^k−1 węzłów wewnętrznych, więc n ≥ 2^bh−1, dając bh ≤ log₂(n+1) i h ≤ 2·log₂(n+1).

Kompletnie sprawiedliwy planista Linuksa (CFS) przechowuje uruchamialne procesy w drzewie czerwono-czarnym kluczowanym wirtualnym czasem działania, dzięki czemu proces o najmniejszym czasie działania (następny do uruchomienia) można znaleźć w czasie O(log n). Menedżer pamięci jądra używa drzew czerwono-czarnych do śledzenia obszarów pamięci wirtualnej (VMA) na proces, a podsystem epoll używa ich do efektywnego zarządzania deskryptorami plików.

Drzewo 2-3-4 (lub B-drzewo rzędu 4) przechowuje 1–3 klucze na węzeł z 2–4 dziećmi, utrzymując idealny balans. Każde drzewo 2-3-4 mapuje się dokładnie na drzewo czerwono-czarne: węzeł 2 staje się pojedynczym czarnym węzłem; węzeł 3 staje się czarnym węzłem z czerwonym dzieckiem; węzeł 4 staje się czarnym węzłem z dwojgiem czerwonych dzieci. Ta odpowiedniość daje alternatywny dowód poprawności drzewa czerwono-czarnego i stanowi podstawę wariantu drzewa LLRB (lewoskrętnego czerwono-czarnego).

Wariant LLRB, spopularyzowany przez Roberta Sedgewicka (2008), dodaje ograniczenie, że czerwone łącza zawsze skręcają w lewo (czerwony węzeł jest zawsze lewym dzieckiem). Redukuje to liczbę przypadków strukturalnych do obsłużenia podczas wstawiania i usuwania z około 6–8 do 3, dając implementacje o mniej więcej 50 liniach kodu w porównaniu z ponad 200 dla standardowego sformułowania Cormena-Leisersona-Rivesta. TreeMap w Javie używa standardowego sformułowania; niektóre biblioteki języków funkcyjnych preferują LLRB.

Tak. Ponieważ każde wstawienie lub usunięcie modyfikuje tylko O(log n) węzłów (wzdłuż ścieżki od korzenia do dotkniętego liścia), trwałe drzewo czerwono-czarne można stworzyć przez kopiowanie ścieżki: duplikowanie jedynie O(log n) węzłów, które się zmieniają, i współdzielenie reszty. Daje to czas i pamięć O(log n) na operację z pełną historią wersji i jest wykorzystywane w trwałych funkcyjnych strukturach danych, takich jak posortowane mapy w Clojure.

Usuwanie najpierw wykonuje standardowe usuwanie BST (zastępując węzeł jego następnikiem in-order, jeśli ma dwoje dzieci). Jeśli usunięty węzeł lub jego zastępca był czerwony, nie dochodzi do naruszenia czarnej wysokości. Jeśli usunięty zostanie czarny węzeł, deficyt „podwójnej czerni” propaguje się w górę i jest rozwiązywany przez sześć przypadków analizy koloru rodzeństwa i bratanków, z których każdy albo przekorzeniuje poddrzewo za pomocą rotacji i przekolorowania, albo przesuwa deficyt w górę. Wystarczą co najwyżej trzy rotacje.