Drzewo czerwono-czarne

Drzewo czerwono-czarne – rodzaj samoorganizującego się binarnego drzewa poszukiwań – struktury danych stosowanej w informatyce najczęściej do implementacji tablic asocjacyjnych. Została ona wynaleziona przez Rudolfa Bayera w 1972 roku, który nazwał je symetrycznymi binarnymi B-drzewami. Współczesną nazwę oraz dokładne zbadanie ich właściwości zawdzięcza się pracy A dichromatic framework for balanced trees z 1978 roku autorstwa Leo J. Guibasa oraz Roberta Sedgewicka.

Drzewa czerwono-czarne są skomplikowane w implementacji, lecz charakteryzują się niską złożonością obliczeniową elementarnych operacji, takich jak wstawianie, wyszukiwanie czy usuwanie elementów z drzewa.

Problem

Podstawowe binarne drzewo poszukiwań pozwala na szybkie wyszukiwanie porównywalnych danych, np. liczb dzięki zorganizowaniu ich w formę drzewa binarnego, przez co czas wykonywania elementarnych operacji jest uzależniony od średniej głębokości h takiego drzewa i wynosi O(h). Jednak drzewo takie nie posiada żadnych mechanizmów, które dążą do jego zrównoważenia, przez co nietrudno jest uzyskać słabo rozgałęzioną strukturę o dużej głębokości. Czas wykonywania operacji będzie wtedy niewiele lepszy, niż dla zwykłych list.

Drzewo czerwono-czarne jest rozszerzeniem podstawowej struktury o algorytm równoważenia wykonywany po każdej operacji INSERT oraz DELETE. W przypadku tej struktury elementy-liście nie przechowują żadnych informacji, dlatego często w ich miejsce wprowadza się dla zaoszczędzenia pamięci i uproszczenia kodu pojedynczego wartownika.

Właściwości

Przykład drzewa czerwono-czarnego

W drzewie czerwono-czarnym z każdym węzłem powiązany jest dodatkowy atrybut „kolor”, który może być czerwony lub czarny. Oprócz podstawowych własności drzew poszukiwań binarnych, wprowadzone zostały kolejne wymagania, które trzeba spełniać:

1. Każdy węzeł jest czerwony albo czarny.
2. Korzeń jest czarny.
3. Każdy liść jest czarny (Można traktować nil jako liść).
4. Jeśli węzeł jest czerwony, to jego synowie muszą być czarni.
5. Każda ścieżka z ustalonego węzła do każdego z jego potomków będących liśćmi liczy tyle samo czarnych węzłów.

Wymagania te gwarantują, że najdłuższa ścieżka od korzenia do liścia będzie co najwyżej dwukrotnie dłuższa, niż najkrótsza. Wynika to wprost z własności:

1. Zgodnie z własnością 4, żadna ścieżka nie zawiera dwóch czerwonych węzłów z rzędu, jednak może zawierać czarne. Stąd najkrótsza ścieżka od węzła X zawiera wyłącznie n czarnych węzłów.
2. Zgodnie z własnością 5, druga ścieżka wychodząca z węzła X musi zawierać także n czarnych węzłów. Jedynym sposobem, aby miała ona inną łączną długość, jest umieszczenie pomiędzy każdą parą węzłów czarnych węzła czerwonego.
3. Zgodnie z własnością 3, liść kończący obie ścieżki musi być czarny. Jeżeli węzeł X jest czarny, wtedy w ścieżce możemy rozmieścić co najwyżej n-1 węzłów czerwonych, w przeciwnym zaś razie będziemy mieli w niej n czerwonych węzłów (wliczając w to sam X).

Zatem łączna długość drugiej ścieżki może wynieść co najwyżej 2n, gdzie n jest długością pierwszej ścieżki zbudowanej wyłącznie z węzłów czarnych.

Można udowodnić, że dla n węzłów głębokość drzewa czerwono-czarnego h wyniesie najwyżej 2 log (n+1), przez co elementarne operacje będą wykonywać się w czasie O(log n).

Operacje

Efekt działania rotacji w lewo i w prawo

Podstawowymi operacjami służącymi do reorganizacji drzewa są operacje rotacji w lewo oraz rotacji w prawo przedstawione na rysunku obok. Rotacja w lewo powoduje spłynięcie danego węzła na lewo w dół i wysunięcie do góry jego prawego syna. Rotacja w prawo zachodzi w drugą stronę - węzeł spływa w prawo, zaś w górę wyciągany jest jego lewy syn. Ze schematu widać, że podczas rotacji nie trzeba przepinać poddrzew a oraz c, natomiast poddrzewo b przenoszone jest między węzłami, zależnie od kierunku rotacji. Można przyjąć, że każda rotacja wykonuje się w czasie O(1).

Rotacja w prawo węzła X jest wykonalna, jeżeli jego lewy syn istnieje. Odpowiednio, możemy wykonać rotację w lewo, jeżeli X posiada prawego syna. Obie rotacje są operacjami odwracalnymi. Na poziomie rotacji nie uwzględniamy kolorowania węzłów, jest ono poprawiane później niezależnie.

Wstawianie

Wstawianie elementu do drzewa składa się z trzech kroków:

1. Umieszczenie elementu za pomocą standardowego algorytmu dla drzew poszukiwań binarnych.
2. Pokolorowanie nowego węzła na czerwono.
3. Przywrócenie własności czerwono-czarnych.

Przywracanie własności rozpoczynamy ze wskaźnikiem z, który początkowo wskazuje na czerwony węzeł, który właśnie dodaliśmy. Kończymy je, gdy rodzic węzła z będzie czarny, zatem podczas każdej iteracji wiemy także, że rodzic jest czerwony. W algorytmie musimy rozważyć sześć przypadków, przy czym wystarczy rozpatrywać tylko trzy. Druga trójka jest ich symetrycznym odbiciem, a my wybieramy odpowiedni przypadek zależnie od tego, czy z jest lewym, czy prawym synem swojego rodzica. Poniżej rozpatrzymy jedynie przypadki, gdy ojciec z jest lewym synem swojego ojca. Możliwe są wtedy następujące sytuacje:

1. Brat ojca (stryj) węzła z jest czerwony.
2. Stryj węzła z jest czarny i z jest prawym synem.
3. Stryj węzła z jest czarny i z jest lewym synem.

Aby rozwiązać pierwszy przypadek, kolorujemy zarówno ojca, jak i jego brata na czarno, a następnie przesuwamy z na ich ojca, którego kolorujemy na czerwono:

z.parent.color = black;               // kolorujemy ojca na czarno
z.parent.parent.right.color = black;  // kolorujemy prawego brata ojca na czarno
z = z.parent.parent;                  // przenosimy się dwa poziomy do góry do ojca ojca.
z.color = red;                        // i kolorujemy go na czerwono

Przypadki 2 i 3 nie wykluczają się wzajemnie, a wręcz przeciwnie. Przypadek 2 możemy bowiem rozwiązać, sprowadzając go do przypadku 3: ustawiamy z na ojca dotychczasowego z i wykonujemy jego rotację w lewo:

z = z.parent;     // przesuwamy się na ojca
left-rotate(z);   // wykonujemy rotacje w lewo

Rozwiązanie przypadku 3 polega na przekolorowaniu ojca z na czarno, jego ojca na czerwono i wykonaniu na tymże ojcu ojca rotacji w prawo:

z.parent.color = black;         // ojciec na czarno
z.parent.parent.color = red;    // jego ojciec na czerwono
right-rotate(z.parent.parent);  // rotacja w prawo ojca ojca.

Wskaźnika z już nie przesuwamy. Zauważmy, że po rozwiązaniu przypadku 3 element z jest czerwony, zaś jego ojciec czarny, co oznacza jednocześnie zakończenie przywracania własności czerwono-czarnych.

Przypadki dla sytuacji, gdy ojciec z jest prawym synem swego ojca wyglądają analogicznie. Należy jedynie odwrócić kolejność wszystkich operacji (lewo → prawo, prawo → lewo).

Usuwanie

Do usuwania węzła z wykorzystujemy standardowy algorytm usuwania elementu z drzewa poszukiwań binarnych z wprowadzoną jedną modyfikacją. Jeśli usuwany węzeł y (mający zawsze co najwyżej jednego syna x) jest czarny, drzewo traci właściwości czerwono-czarne, które muszą zostać przywrócone:

jeśli y.color == BLACK wtedy
    delete-restore(x);
remove(y);

Procedura delete-restore() przywraca własności czerwono-czarne przed wykonaniem fizycznego usunięcia, zaczynając od jedynego syna usuwanego węzła y. Jeśli y nie miał synów, x jest wtedy czarnym wartownikiem. Mogą zajść trzy przypadki:

1. Jeśli y był korzeniem, wtedy nowym korzeniem zostaje węzeł czerwony, co narusza własność 2.
2. Jeśli x oraz y.parent były czerwone, naruszamy własność 4, gdyż czerwony węzeł będzie mieć czerwonego syna.
3. Usunięcie y sprawia, że wszystkie przechodzące przez niego ścieżki będą mieć o jeden czarny węzeł mniej, co narusza własność 5.

Po fizycznym usunięciu węzła można rozróżnić następujące przypadki:

• jeśli x jest czerwony, wówczas nadajemy mu kolor czarny,
• jeśli x jest już czarny, wówczas dokonujemy naprawy drzewa, rozważając przypadki zależne od koloru ojca, brata i jego obu synów.

Podobne struktury

1. Alternatywnym sposobem równoważenia BST jest użycie drzew AVL. AVL jest prostsze w implementacji i daje bardziej zrównoważone drzewo, lecz z tego powodu operacje usuwania są bardziej kosztowne; w najgorszym przypadku będzie konieczne przejście całej ścieżki od liścia do korzenia, podczas gdy przywrócenie własności czerwono-czarnych wymaga wykonania maksymalnie dwóch rotacji.

Zobacz też

Wikipedia:

• binarne drzewo poszukiwań
• drzewo AVL
• drzewo splay
• drzewo statystyk pozycyjnych

Internet:

• Wizualizacja pokazująca istotę drzew CC, z wyjaśnieniem poszczególnych kroków
• Wysoko wydajna implementacja drzew czerwono-czarnych w języku C++ z wykorzystaniem tablicy liniowej