Mariusz Pluciński

Informatyka, gr. 1

Projekt ppp09c – drzewo czerwono-czarne

Drzewo czerwono-czarne – sprawozdanie

1 Opis algorytmu

Drzewo czerwono-czarne jest w istocie rozszerzeniem struktury zwykłego drzewa binarnego 

przez dodanie do niego tzw. własności czerwono-czarnych. Zmodyfikowane w ten sposób drzewo 
charakteryzuje się zautomatyzowanym równoważeniem po każdej operacji wstawiania/usuwania 
elementów. Dzięki temu że drzewo jest cały czas zrównoważone, operacja wyszukiwania przebiega 
znacznie szybciej niż w zwykłym, niezrównoważonym drzewie.

1.1 Struktura binarnego drzewa poszukiwań

Binarne drzewo poszukiwań, w stosunku do zwykłych drzew, posiada kilka dodatkowych 

założeń:

1. Stopień każdego wierzchołka jest nie większy od 3

Oznacza to, że każdy wierzchołek ma co najwyżej dwóch synów.

2. Wyróżnia się lewego i prawego syna, przy czym lewy syn zawsze ma wartość klucza nie 

większą od wartości klucza swojego rodzica, a prawy syn wartość nie mniejszą od wartości 
klucza swojego rodzica.
Przy czym w programie prezentacyjnym przyjęto założenie o unikalności kluczy, w celu 
uproszczenia implementacji.

Istotną cechą binarnego drzewa poszukiwań jest jego zrównoważenie. Drzewo jest 

zrównoważone, gdy dla każdego węzła różnica w wysokości jego lewego i prawego poddrzewa 
wynosi co najwyżej 1. Cecha ta jest ważna, gdyż operacja wyszukiwania (jak również dodawania i 
usuwania) elementów wykazuje najbardziej optymalne działanie w przypadku drzew 
zrównoważonych. Samo binarne drzewo poszukiwań nie przewiduje jednak automatycznego 
równoważenia, tak więc najczęściej wykorzystuje się jego rozszerzenia, wprowadzające takie 
możliwości. Jednym z takich rozszerzeń jest właśnie drzewo czerwono-czarne.

1.2 Własności czerwono-czarne

Drzewo czerwono-czarne rozszerza strukturę zwykłego binarnego drzewa poszukiwań przez 

wprowadzenie kilku dodatkowych założeń, gwarantujących względne zrównoważenie drzewa:

1. Każdemu z węzłów zostaje przypisany dodatkowy atrybut – kolor – o dwóch 

dopuszczalnych wartościach: czerwony lub czarny.

2. Korzeń drzewa jest zawsze czarny
3. Każdy pusty liść jest traktowany jako czarny
4. Wszyscy synowie każdego czerwonego węzła są czarni
5. Każda ścieżka prowadząca z korzenia do dowolnego liścia zawiera tę samą liczbę czarnych 

węzłów (inaczej: czarna wysokość każdego węzła od korzenia jest taka sama). Właśnie ta 

właściwość gwarantuje utrzymanie zrównoważenia w drzewie.

1.3 Operacja rotacji

Ważną rolę w implementacji operacji wstawiania i usuwania elementów w drzewie 

czerwono-czarnym (jak również w wielu innych algorytmach równoważenia drzew) pełni operacją 
rotacji. Wyróżnić można operację rotacji w lewo lub w prawo. 

Rotacja węzła x w lewo polega na zamianie jego pozycji w drzewie z pozycją jego prawego 

syna - y. Węzeł x staje się wówczas lewym synem węzła y, węzeł y zajmuje natomiast pozycję 
węzła x w relacji z jego dawnym rodzicem.  Zależność pomiędzy węzłem x i jego lewym synem nie 
ulega zmianie, podobnie jak zależność pomiędzy węzłem y a jego prawym synem. Natomiast lewy 
syn węzła y staje się prawym synem węzła x, przenosząc ze sobą całe poddrzewo. 

Rotacja węzła w prawo przebiega analogicznie, z tym że wymianie pozycji podlega węzeł x 

oraz jego lewy syn. Zależności i operację są wówczas symetryczne do tych opisanych wyżej.

Rotacja w lewo węzła jest wykonalna jeżeli posiada on prawego syna. Analogicznie rotacja 

w prawo jest wykonalna, jeżeli węzeł posiada lewego syna.

1.4 Procedura wyszukiwania

Operacja wyszukiwania w drzewie czerwono-czarnym przebiega w sposób identyczny co w 

zwykłym drzewie binarnym. 

Należy rekurencyjnie przyrównywać poszukiwaną wartość klucza do wartości klucza 

danego węzła. Jeżeli są równe, to szukana wartość została właśnie znaleziona.

Jeżeli wartość poszukiwanego klucza jest mniejsza od wartości klucza w sprawdzanym 

węźle, to należy sprawdzić czy dany węzeł ma lewego syna. Jeżeli nie ma, to żaden węzeł w 
drzewie nie posiada takiej wartości klucza. Jeżeli ma, należy przejść do tego syna i na nim wykonać 
sprawdzanie rekurencyjne.

Analogicznie, jeżeli wartość poszukiwanego klucza jest większa od wartości klucza w 

sprawdzanym węźle, należy sprawdzić czy sprawdzany węzeł posiada prawego syna. Jeżeli nie ma, 
to żaden węzeł w drzewie nie posiada takiej wartości klucza. Jeżeli ma, należy przejść do tego syna 
i na nim wykonać sprawdzanie rekurencyjne.

Algorytm rozpoczyna się od sprawdzenia korzenia, następnie przechodzi on rekurencyjnie 

po niższych gałęziach, kończąc się zgodnie z podanymi warunkami. Możliwe jest również 
skonstruowanie wersji iteracyjnej algorytmu.

1.5 Procedura wstawiania

Procedura wstawiania elementu do drzewa czerwono-czarnego jest rozbudowana w 

stosunku do procedury wstawiania w zwykłym drzewie binarnym. 

Wstawianie wartości do zwykłego drzewa binarnego jest operacją zbliżoną do operacji 

wyszukiwania, z taką zmianą, że w przypadku stwierdzenia nie istnienia danej wartości w drzewie 
zostaje ona wstawiona właśnie w to miejsce gdzie stwierdzono jej brak. Natomiast postępowanie w 
przypadku znalezienia klucza o takiej wartości jaką chcemy wstawić zależy od tego czy przyjęto 
założenie o unikalności kluczy w drzewie czy nie.

Nowo wstawiony węzeł jest zawsze kolorowany na czerwono. Potem następuje operacja 

przywrócenia własności czerwono-czarnych.

Algorytm przywracania właściwości czerwono-czarnych rozpoczyna się ze wskaźnikiem x 

ustawionym na nowo wstawiony węzeł. Na początek sprawdza się, czy rodzic węzła x jest 

czerwony (gdyż tylko wtedy własności drzewa zostały zaburzone). Jeżeli nie, drzewo uznaje się za 
zrównoważone i kończy pracę algorytmu wstawiania.

Dalszy tok postępowania zależy od wystąpienia jednego z sześciu warunków, związanych z 

kolorami węzłów leżących na pobliskich nowo wstawionemu gałęziach. Zazwyczaj rozpatruje się 
jedynie trzy warunki, ponieważ druga trójka jest ich ich symetrycznym odbiciem, a przynależność 
do drugiej z nich zmienia jedynie kierunek wykonywanych rotacji na przeciwny. Poniższe opisy 
odnoszą się do przypadku gdy ojciec węzła x jest lewym synem swojego ojca (dziadka węzła x):

1. Brat ojca węzła x jest czerwony

W takiej sytuacji należy pokolorować zarówno ojca węzła x jak i jego brata na czarno. 
Następnie ustawić wskaźnik x na ojca ojca węzła x (tzn. dziadka) i rozpocząć algorytm 
przywracania własności na tym węźle.

2. Brat ojca węzła x jest czarny, a x jest prawym synem swojego ojca

Ten przypadek zazwyczaj sprowadza się do przypadku trzeciego, poprzez wykonanie na 
ojcu węzła x obrotu w lewo.

3. Brat ojca węzła x jest czarny, a x jest lewym synem swojego ojca

W takiej sytuacji należy pokolorować ojca węzła x na czarno, dziadka węzła x na 
czerwono, a następnie wykonać na dziadku węzła x obrotu w prawo.

Powyższe przypadki (wraz z ich trzema symetrycznymi wersjami) są w pełni wystarczające, 

aby zapewnić utrzymanie właściwości czerwono-czarnych przez drzewo, a zgodnie z założeniem 5. 
również utrzymanie zrównoważenia przez drzewo.

1.6 Procedura usuwania

Procedura usuwania węzła z drzewa czerwono-czarnego, podobnie jak pozostałe operacje 

na tym drzewie, stanowi rozszerzenie tej operacji dla zwykłych drzew binarnych.

Postępowanie podczas usuwania węzła w drzewie binarnych zależy od tego, ilu ma on 

synów:

•

żadnego – nie są wymagane żadne dodatkowe operacje, węzeł może zostać usunięty 
bezpośrednio

•

jednego – podstawić syna usuwanego węzła  w miejsce relacji rodzica usuwanego węzła z 
usuwanego węzła

•

dwóch – należy znaleźć następnik usuwanego węzła (najbardziej lewy element w jego 
prawym poddrzewie), następnie wstawić następnika w miejsce usuwanego węzła.

Następnie, o ile usuwany węzeł był czarny, należy wykonać algorytm przywracania 

własności czerwono-czarnych, za wskaźnik początkowy przyjmując jedynego syna usuwanego 
węzła.

2 Opis programu

Program prezentacyjny przedstawia strukturę drzewa czerwono-czarnego w formie 

graficznej. Węzły zawierają przypisane im wartości liczbowe oraz kolor. Zachowana jest również 
hierarchia węzłów.

Programem steruje się przy pomocy poleceń wpisywanych z klawiatury. Rozpoznawany 

jest następujący zestaw poleceń:

insert x – (za x podstawić należy wartość liczbową z zakresu 1-255) – wstawienie 

elementu o wartości klucza x do drzewa.

random x – (za x podstawić należy wartość liczbową z zakresu 1-255) – wstawienie x 

elementów (każdy o losowej wartości) do drzewa.

find x – (za x podstawić należy wartość liczbową z zakresu 1-255) – odszukanie elementu 

o wartości klucza x w drzewie.

delete x – (za x podstawić należy wartość liczbową z zakresu 1-255) – usunięcie elementu 

o wartości klucza x z drzewa.

exit – koniec pracy programu.

3 Przedstawienie działania algorytmu dla przykładowych 

danych

W drzewie czerwono-czarnym operacją o niewątpliwie największym stopniu komplikacji 

jest wstawianie elementów. Poniższy opis odnosi się do tego właśnie algorytmu.

Rozważmy proste drzewo z kilkoma węzłami i zachowanymi własnościami czerwono-

czarnymi. 

Dla tak przygotowanego drzewa prześledźmy krok po kroku procedurę wstawiania 

elementu o wartości 89.

Na początek, umieszczamy węzeł 89 za pomocą standardowej procedury dla drzew 

binarnych. Węzeł 89 staje się wówczas prawym synem węzła 82. Nowy węzeł kolorujemy zawsze 
na czerwono.

Następnie stwierdzamy, że zarówno nowy węzeł (89) jak i jego rodzic (82) mają kolor 

czerwony. Należy więc  dokonać operacji przywrócenia własności czerwono-czarnych.

Obrany przypadek zależy od koloru brata ojca. W opisywanym wypadku węzeł 82 nie ma 

brata, zakładamy więc obecność w tym miejscu czarnego wartownika. Jako że 89 jest prawym 
synem 82, zachodzi przypadek nr 3. Zgodnie z procedurą obsługi tego przypadku, kolorujemy ojca 
(82) na czarno, dziadka (58) na czerwono, a następnie wykonujemy na dziadku obrót w lewo.

Ostatecznie, drzewo po wykonaniu operacji wygląda następująco: