Drzewo czerwono-czarne

Z Wikipedii

Drzewo czerwono-czarne to rodzaj samoorganizującego się drzewa poszukiwań binarnych - struktury danych stosowanej w informatyce stosowanej często 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.

Spis treści 1 Problem 2 Właściwości 3 Podobne struktury 4 Operacje 4.1 Wstawianie 4.2 Usuwanie 5 Zobacz także 6 Przypisy

[edytuj] Problem

Podstawowe drzewo poszukiwań binarnych 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) ^[1]. 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.

[edytuj] Właściwości

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 lub czarny.
2. Korzeń jest czarny.
3. Każdy liść jest czarny.
4. Jeśli węzeł jest czerwony, to jego synowie muszą być czarni.
5. Każda ścieżka z ustalonego węzła do liścia 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 pod rząd, 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 x 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) ^[1].

[edytuj] 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 dodawania bądź 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.
2. Drzewo splay dąży do zrównoważenia przez wyciąganie elementu, na którym operowaliśmy, do korzenia. Operacją modyfikującą drzewo jest także SEARCH, czyli wyszukiwanie elementu, przez co uzyskujemy rodzaj cache'u lub historii operacji.

[edytuj] Operacje

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.

[edytuj] 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 swego 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 sie dwa poziomy do gory 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 sie 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).

[edytuj] Usuwanie

Algorytm usuwania węzła z składa się z trzech części:

1. Wyznaczenie węzła y do usunięcia standardowym algorytmem usuwania elementu z drzewa poszukiwań binarnych.
2. Jeżeli y jest czarny, przywracanie własności czerwono-czarnych.
3. Fizyczne usunięcie y.

Jeżeli y jest czerwony, jego fizyczne usunięcie nie zaburzy żadnej z własności drzewa:

1. nie zmieniła się czarna wysokość drzewa.
2. żadne czerwone węzły nie stały się sąsiednie.
3. y nie mógł być korzeniem drzewa.

Do algorytmu przywracającego własności czerwono-czarne po usunięciu przekazujemy albo węzeł x będący jedynym synem y, albo węzeł wartownika, który po wykonaniu kroku 1 powinien posiadać wskazanie na y jako swojego ojca.

To jest tylko zalążek artykułu. Jeśli potrafisz, rozbuduj go.

[edytuj] Zobacz także

Wikipedia:

• Drzewo poszukiwań binarnych
• Drzewo AVL
• Drzewo splay

Internet:

• Aplet pokazujący istotę drzew CC

Przypisy