Drzewa czerwono-czarne
Wstęp
Pojęcie drzewa czerwono-czarnego (red-black tree) zapoczątkował Rudolf Bayer w książce z 1972 r. pt. „Symmetric Binary B-Trees: Data Structure and
Maintenance Algorithms”. Nową strukturę Bayer nazywał początkowo symetrycznymi drzewami binarnymi. Później zagadnieniu przyglądali się L. J. Guibas i R.
Sedgewick, którzy dodali własności czerwono-czarne.
Drzewa RB są szczególnym przypadkiem drzew przeszukiwań binarnych (BST). Aby w pełni zrozumieć artykuł należy zapoznać się z podstawowymi pojęciami/operacjami na drzewach BST.
Podstawowe pojęcia
Definicja:
__Drzewo czerwono-czarne __(RB) jest to drzewo przeszukiwań binarnych (BST) o następujących 5 własnościach:
- każdy węzeł ma jeden z dwóch kolorów: czerwony lub czarny,
- korzeń ma kolor czarny,
- każdy pusty liść (NIL) jest czarny,
- synowie czerwonego wierzchołka są czarni,
każda ścieżka z korzenia do jakiegokolwiek liścia zawiera tą samą liczbę czarnych węzłów.
Ostatni podpunkt jest własnością, która powoduje zrównoważenie całego drzewa. Poprzez wymuszenie identycznej „czarnej wysokości” dla węzłów na tej samej wysokości, wymuszana jest tym samym wysokość całego drzewa. Czarna wysokość węzła v, oznaczana jako bh(v), jest to liczba czarnych węzłów znajdujących się na dowolnej ścieżce z węzła v (wykluczając v) do któregokolwiek liścia.
Przykładowe drzewo czerwono-czarne.
Wszystkie powyższe własności, zastosowane dla drzewa przeszukiwań binarnych, tworzą nową, udoskonaloną, strukturę danych. Drzewa czerwono-czarne, lepiej niż drzewa innego typu, sprawdzają się w szybkim wyszukiwaniu elementów. Operacje takie jak dodanie/usuwanie, wyszukiwanie elementu, wyszukiwanie elementu najmniejszego/największego, wskazanie następnika/poprzednika danego elementu działają w czasie O(lg n).
Wyszukiwanie
Jako że, drzewo czerwono-czarne jest drzewem przeszukiwań binarnych, wyszukiwanie elementu o kluczu k odbywa się tak samo jak wyszukiwanie w standardowym drzewie BST. Rekurencyjna funkcja Search(v, k) jako parametry przyjmuje wskaźnik do korzenia v oraz wartość klucza k do znalezienia. Funkcja zwraca wskaźnik do elementu o wartości klucza k lub wartość NIL, jeżeli taki klucz nie został znaleziony:
Search(v, k)
if (v jest liściem) lub (key[v] = k)
then return v
if k < key[v]
then return Search(left[v], k)
else return Search(right[v], k)
Rotacja
Rotacja jest kluczową procedurą wykorzystywaną w procesie wstawiania i usuwania. Schemat przedstawia działanie 2 odmian: lewej i prawej rotacji. Rotacja zachowuje porządek inorder kluczy. Lewa rotacja może być wykonana tylko, gdy prawy syn x jest niepusty. Lewa rotacja polega na „obrocie” wokół krawędzi między węzłami x i y. W wyniku rotacji y staje się nowym korzeniem poddrzewa, x staje się jego lewym synem, a lewy syn y zostaje prawym synem węzła x.
Ogólny schemat rotacji.
Wstawianie
Operacja wstawiania nowych elementów jest operacją dość skomplikowaną. W odróżnieniu od drzew BST, wstawiając element musimy pamiętać, aby zachować zrównoważenie drzewa. Wstawienie elementu w dowolnym miejscu może powodować zaburzenie struktury drzewa RB. Aby uniknąć pomyłek należy zapamiętać następujące własności:
- Początkowo wstawiamy element tak, jak do standardowego drzewa BST.
- Kolor każdego nowo dodanego elementu jest czerwony.
- Jeżeli rodzic wstawionego węzła jest czarny to własność drzewa została zachowana.
- Jeżeli rodzic wstawionego węzła jest czerwony to własność 4 została zaburzona (rodzic i syn mają kolor czerwony). Aby przywrócić własność należy przekolorować niektóre węzły i zmienić relację (wartości wskaźników) między niektórymi węzłami.
Insert(T, v)
if T = NIL //T jest pustym drzewem
then v jest korzeniem i jest czarny
przerwij
if Search(T, key[v]) = NIL //sprawdzenie, czy elementu v nie ma już w drzewie
then wstaw v do drzewa T tak jak w drzewie BST
pokoloruj v na czerwono
if rodzic v jest czerwony
then przywróć własność drzewa RB wg 3 przypadków poniżej
else przerwij //element v jest już w drzewie
Przywracanie własności drzewa RB __następuje tylko w sytuacji, gdy rodzic dodanego węzła jest czerwony. Oto __3 możliwe przypadki takiego zdarzenia:
Przypadek 1. CZERWONY WUJEK
Pierwsza możliwa sytuacja w przypadku czerwonego wujka.
Druga możliwa sytuacja w przypadku czerwonego wujka.
Opis:
Nowo dodany węzeł jest zaznaczony niebieską obwódką. Aby pozbyć się ustawienia dwóch czerwonych węzłów (ojciec-syn) zmieniamy kolor ojca, dziadka oraz pradziadka dodanego węzła. W tym przypadku pradziadek powinien zmienić kolor na czerwony, jednak mając na uwadze drugą własność drzew RB pradziadek zmienia kolor z powrotem na czarny, gdyż jest korzeniem.
Przypadek 2. CZARNY WUJEK, PRAWY SYN
kolejność: a - b - c - d
Opis:
Nowo dodany węzeł jest zaznaczony niebieską obwódką. W pierwszej kolejności poddrzewo przechodzi proces rotacji (b-c) tak, że nowy wierzchołek i ojciec zmieniają poziom w drzewie. Po rotacji kolorujemy nowy węzeł na czarno, a stary korzeń na czerwono (d). Jak widać na rysunku przed rotacją wysokość drzewa wynosiła 2, po rotacji zmniejszyła się do 1.
Przypadek 3. CZARNY WUJEK, LEWY SYN
kolejność: a - b - c
Opis:
Przypadek 3 jest bardzo zbliżony do przypadku 2. Faktycznie został wykonany podobny zabieg, tylko dla innego węzła. Ponownie dokonano zabiegu rotacji, ale tym razem ojciec został umieszczony na szczycie poddrzewa, a nie nowo dodany wierzchołek. Podobnie jak poprzednio zmieniono kolory odpowiednich węzłów. Wysokość poddrzewa zmniejszyła się o jeden.
PRZYKŁAD WSTAWIANIA NOWEGO WĘZŁA DO DRZEWA CZERWONO-CZARNEGO:
Oryginalne drzewo. W następnych rysunkach czarne puste liście zostały pominięte ze względu na czytelność schematu.
Wstawiamy wierzchołek oznaczony jako 4. Własność drzewa RB została zaburzona – czerwony zarówno ojciec jak i syn. Zaznaczono nowy węzeł jako x i jego wujka jako y. y jest czerwony, więc rozważamy przypadek 1.
Zmieniono kolor węzła 5, 7 i 8.
W następnym kroku x wskazuje na swojego dziadka – 7. Ojciec x jest nadal czerwony, więc nie została przywrócona własność drzewa RB. Oznaczamy wujka x jako y. W tej sytuacji wujek jest czarny, więc rozważamy przypadek 2.
x wskazuje teraz na swojego ojca – 2, po czym zastosowano rotację lewą.
W dalszym ciągu nie jest to drzewo czerwono-czarne.
Zmieniono kolory węzłów 7 i 11 oraz zastosowano rotację prawą.
Dopiero tak powstałe drzewo posiada wszystkie własności drzewa RB.
Usuwanie
Podobnie, jak w przypadku wstawiania, usuwanie wymaga dodatkowej uwagi w celu zachowania zrównoważenia drzewa. Tym razem, zamiast martwić się o rodzica wstawianego elementu, skupić należy uwagę na kolorze usuwanego węzła. Należy pamiętać, że:
- jeżeli usuwany wierzchołek jest czerwony, czarna wysokość drzewa nie jest zakłócona,
- jeżeli usuwany wierzchołek jest czarny powoduje on zakłócenie zrównoważenia drzewa i należy naprawić czarną wysokość dla każdej ścieżki w drzewie.
Delete(T, v)
if v jest liściem
then usuń v //zostaje zastąpiony czarnymi pustymi liśćmii
if v jest czerwony //nie ma zmiany czarnej wysokości
then koniec usuwania
if v jest czarny
then zrównoważ drzewo wg 4 przypadków poniżej
else //v nie jest liściem
znajdź najbardziej odpowiednie dziecko u do zamiany
zamień v z u
usuń v //zostaje zastąpiony czarnymi pustymi liśćmi
if v jest czerwony //nie ma zmiany czarnej wysokości
then koniec usuwania
if v jest czarny
then zrównoważ drzewo wg 4 przypadków poniżej
Operację usuwania wykonuje się oczywiście tylko przy założeniu, że wierzchołek v istnieje w drzewie T. 4 przypadki, na które należy zwrócić uwagę w przypadku usuwania czarnego wierzchołka.
Przypadek 1. CZERWONY BRAT
kolejność: a - b - c - d
Opis:
W tym przypadku usunięcie wierzchołka 20 powoduje, ze w jego miejsce trafia syn 10 (b). Drzewo potrzebuje powtórnego zrównoważenia. Po wykonaniu rotacji lewej (c) wierzchołek x oraz jego brat muszą zostać przekolorowane (d).
Przypadek 2. CZARNY BRAT, CZARNY BRATANEK
kolejność: a - b - c
Opis:
W tym przypadku po usunięciu węzła 20, węzeł 10 trafia w jego miejsce. W odróżnieniu od przypadku pierwszego, tutaj następuje zmiana wysokości drzewa. Należy pokolorować x na czarno, brata na czerwono, ojca x na czarno, o ile to już nie zostało zrobione. Taki zabieg może powodować zachwianie własności RB drzewa. Należy sprawdzić czy relacje ojciec-dziadek są zachowane w tym przypadku i dalej w górę drzewa. Jest to jeden z najprostszych przypadków usuwania, gdyż zmienia się tylko kolory węzłów, a nie połączenia między nimi.
Przypadek 3. CZARNY BRAT, LEWY CZERWONY BRATANEK
kolejność: a - b - c - d
Opis:
Po usunięciu wierzchołka 35, węzeł 40 trafia w jego miejsce. Zgodnie z własnością 5 tak powstała drzewo nie jest drzewem czerwono-czarnym (b). Lewy syna brata x (10) jest czerwony, więc należy wykonać zabieg rotacji prawej (c) wokół brata x. Następnie należy zmienić kolor (d). W dalszym ciągu nie ma gwarancji, że tak zmodyfikowane drzewo jest drzewem RB, więc potrzebna jest jeszcze jedna rotacja, tym razem wokół nowego brata x – węzła 10. Ten zabieg jest podobny do sytuacji, gdyby wierzchołek 20 oryginalnie miał czerwonego prawego syna, więc rozważmy przypadek 4.
Przypadek 4. CZARNY BRAT, PRAWY CZERWONY BRATANEK
kolejność: a - b - c - d
Opis:
Powtórnie, 35 jest usuwany, a 40 wchodzi na jego miejsce. Brat x ma czerwone prawe dziecko (przypadek 3d). Po zabiegu rotacji, prawy bratanek jest na szczycie poddrzewa (c). Potrzebna jest zmiana koloru niektórych węzłów. Należy pokolorować starego brata x (20) oraz nowego brata (30) na czarno. X dostaje kolor czarny, a nowy dziadek (10) kolor taki sam jaki miał rodzic x przed rotacja (30 – czerwony).
Linki
- http://www.eli.sdsu.edu/courses/fall95/cs660/notes/RedBlackTree/RedBlack.html
- http://www.oopweb.com/Algorithms/Documents/Sman/Volume/s_rbt.txt - implementacja w C
Bibliografia
- T.H. Cormen - Wprowadzenie do algorytmów.
- Wikipedia - encyklopedia internetowa
Aby dodawać komentarze musisz być zalogowany!