Loading AI tools
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.
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)[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[2].
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 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ć:
- Każdy węzeł jest czerwony albo czarny.
- Korzeń jest czarny.
- Każdy liść jest czarny (Można traktować nil jako liść).
- Jeśli węzeł jest czerwony, to jego synowie muszą być czarni.
- 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:
- 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.
- 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.
- 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].
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:
- Umieszczenie elementu za pomocą standardowego algorytmu dla drzew poszukiwań binarnych.
- Pokolorowanie nowego węzła na czerwono.
- 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:
- Brat ojca (stryj) węzła z jest czerwony.
- Stryj węzła z jest czarny i z jest prawym synem.
- 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:
- Jeśli y był korzeniem, wtedy nowym korzeniem zostaje węzeł czerwony, co narusza własność 2.
- Jeśli x oraz y.parent były czerwone, naruszamy własność 4, gdyż czerwony węzeł będzie mieć czerwonego syna.
- 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.
- 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.
Wikipedia:
- binarne drzewo poszukiwań
- drzewo AVL
- drzewo splay
- drzewo statystyk pozycyjnych
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
