Dziś dokończymy ostatnio omawiane zagadanienie związane z drzewami AVL i powiemy o wstawianiu elementów do tego drzewa. Zawsze po wstawieniu elementu do drzewa AVL należy wykonać 1 rotację pojedynczą, lub podwójną w celu jego zrównoważenia. I tutaj mamy do czynienia z czterema przypadkami charakterystycznymi:

1. Wstawianie węzła do prawego poddrzewa prawego następnika

2. Wstawianie węzła do lewego poddrzewa lewego następnika

3. Wstawianie węzła do lewego poddrzewa prawego następnika

4. Wstawianie węzła do prawego poddrzewa lewego następnika

Popatrzmy na rysunku, jak wygląda wstawianie węzła do prawego poddrzewa prawego nastepnika. Mamy wówczas do czynienia z rotacją lewą węzła A wokół B:

A tak wygląda wstawianie węzła do lewego poddrzewa lewego następnika. Tutaj z kolei mamy do czynienia z rotacją prawą węzła A wokół B:

Teraz kolej na wstawianie węzła do lewego poddrzewa prawego następnika. Tu stosujemy rotację lewą węzła B wokół A i prawą węzła B wokół C:

I ostatnie to wstawianie węzła do prawego poddrzewa lewego następnika. Mamy tu do czynienia z rotacją prawą węzła B wokół A i lewą węzła B wokół C:

Spójrzmy jeszcze na to, jak się równoważy drzewa AVL po wstawieniu węzła. Najpiwer wstawiamy nowy węzeł do lewego poddrzewa węzła Q:

Na drugim rysunku została pokazana podwójna rotacja węzła R (wokół węzła Q i węzła P). Przejdźmy teraz do usuwania elementu z drzewa AVL. Po usunięciu elementu z drzewa AVL może się zdarzyć, że w celu jego zrównoważenia należy wykonać tyle rotacji ile jest poziomów w drzewie. Spójrzmy na cztery przypadki. W pierwszym i drugim mamy do czynienia z pojedyncza rotacją, natomiast w drugim i trzecim - z podwójną:

I teraz jaki jest koszt takiego usunięcia węzła w drzewie AVL. Na pewno rotacje działają w czasie O(1). Ponadto zmieniają się tylko wartości wskaźników, a pozostałe pola węzłów nie sa zmieniane. A teraz jaka jest minimalna liczba wierzchołków n w drzewie AVL o wysokości h. Spójrzmy na wzór:

Stąd można udowodnić, że:

Liczba rotacji wynosi zatem co najwyżej 2 lg n, oraz złożoność obliczeniowa

Równoważenia drzewa AVL po usunięciu węzła wynosi
.

Przejdźmy teraz do kolejnego rodzaju drzewa, a mianowicie do drzew czerwono - czarnych (RB). Drzewo to jest kolejnym rozwinięciem drzewa BST zaraz po AVL. Pierwsza jego publikacja przypada na rok 1972. Powstało ono w celu przyspieszenia operacji przetwarzania przez odpowiednią organizację węzłów w drzewie. Dzięki zastosowanym metodom równoważenia pesymistyczna złożonośc operacji wynosi O(lg n). Drzewo red black powstaje o rozszerzenie drzewa BST o pole koloru (czerwony i czarny). W tym drzewie wszystkie wartości NULL traktujemy jako zewnętrzne węzły drzewa, czyli liście. Zwyczajne węzły tego drzewa zawierające klucze nazywamy węzłami wewnętrznymi drzewa. Oto, jakie to drzewo posiada własności:

1. Każdy węzeł ma kolor czerwony lub czarny.

2. Korzeń ma zawsze kolor czarny.

3. Każdy liść (wskaźnik o wartości NULL) ma kolor czarny.

4. Jeżeli węzeł jest czerwony, to wszystkie jego następniki sa czarne.

5. Dla każdego węzła każda prosta ścieżka od węzła do liścia zawiera jednakową liczbę węzłów czarnych.

I teraz popatrzmy na kilka przykładów:

Stąd widać, że powyższe drzewo jest drzewem czerwono czarnym. Popatrzmy z kolei na poniższy rysunek:

To drzewo z kolei nie jest drzewem czerwono czarnym, ponieważ nie jest spełnione zalożenie 4 i 5. I teraz powiemy sobie o takich trzech pojęciach. Będzie to wysokośc węzła, czarna wysokośc węzła i czarna wysokośc drzewa red black. Wysokośc węzła h(x) to największa liczba węzłów na drodze prostej z węzła x do liści. Z kolei czarna wysokośc węzła, czyli bh(x) to liczba węzłów czarnych (z uwzględnieniem liścia - NULL) na drodze od tego węzła do liścia (z wykluczeniem tego węzła). I na koniecz czarna wysokośc drzewa red black. Jest to czarna wysokośc korzenia danego drzewa.

Dla drzewa czerwono czarnego mamy trzy lematy. Pierwszy mówi o tym, że każde poddrzewo czerwono czarne o korzeniu w dowolnym węźle x posiada co najmniej
węzłów wewnętrznych. To znaczy:
. Drugi lemat mówi o tym, że każdy węzeł x o wysokości h(x) ma czarną wysokość bh(x), przy czym
. No i ostatni z lematów mówi o tym, że drzewo czerowno czarne o n węzłach wewnętrznych ma wysokość h nie większa niż
, co znaczy, że
. Przykładowo dla:

Przejdźmy teraz do operacji wykonywanych na drzewie czerwono czanrym. Na początek kilka słów o wyszukiwaniiu elementów w tym drzewie. Ponieważ struktura drzewa nie ulega zmianie, operacja wyszukiwania realizowana jest tak samo, jak w zwykłym drzewie BST, czyli realizowana jest w trzech punktach:

1. Wstaw węzeł we właściwe miejsce (z zachowaniem własności dzrewa BST).

2. Pokoloruj węzeł na czerwono (Z wskazuje na nowy węzeł).

3. Jeśli trzeba wykonaj korektę drzewa w zależności od przypadku (jednego z trzech) który wystapił.

Przywracanie własności drzewa czerwono czarnego następuje tylko w sytuacji, gdy poprzednik dodanego węzła jest czerwony. No i teraz jakie mamy przypadki. Przypadek zerowy mówi o tym, że jeśli Z jest korzeniem, to przekoloruj nowo wstawiony węzeł na czarno. W pierwszym z przypadków zarówno poprzednik (ojciec), jak i bezposredni sasiad popraednika (wuj) są czerwone:

W drugim przypadku poprzednik (ojciec) jest czerwony, a wuj jest czarny. Ponadto Z i jego ojciec są następnikami po przeciwnych stronach (to jest, że Z jest prawym następnikiem podczas, gdy ojciec lewym lub odwrotnie).

I trzeci przypadek, gdy poprzednik (ojciec) jest czerwony, a wuj jest czarny. Ponadto Z i jego ojciec sa następnikami po tej samej stronie (prawymi, lub lewymi).

I teraz jak dokonuje się wstawiania dla tych trzech przypadków. Dla pierwszego najpierw kolorujemy poprzednik (ojca) i jego sasiada (wuja) na czarno. Następnie kolorujemy poprzednika ojca (dziadka) na czerwono. I na koniec ustawiamy Z na poprzednika ojca (dziadka):

Teraz przypadek drugi. Tutaj na początku stosujemy podwójną rotację (lewą - Z wokół P i prawą - Z wokół G). Natomiast potem przekolorowujemy G i Z:

No i przypadek trzeci. Tutaj aby wstawić element należy dokonac rotacji P wokół G, oraz przekolorować P i G:

I jeszcze spójrzmy na kilka przykładów zamiany drzew na czerwono czarne.W pierwszym przypadku mamy do czynienia z przypadkiem numer 3. w dwóch następnych - z przypadkiem 1, a w ostatnim - z przypadkiem numer 2.

Teraz z kolei przejdźmy do usuwania węzła z drzewa. Jakie zmiany wywołuje takie usunięcie. W przypadku węzła czerwonego czarne wysokości węzłów nie zmieniają się, a ponadto można stwierdzić, że usuwany węzeł nie mógł być korzeniem, bo byłby koloru czarnego. W przypadku węzła czarnego - ścieżki, na których leżał usuniety węzeł mają o jeden czarny węzeł mniej (złamanie założeń 4 i 5). Ponadto jeśli usuwany węzeł był korzeniem, może zastapić go węzeł koloru czerwonego (złamanie zasady 2). Rozpatrzmy usuwanie typu bottom up. Usuwanie przebiega tu analogicznie do operacji w drzewie BST. Korekta przy usuwaniu węzła czarnego przebiega nastepująco. Mamy cztery założenia, że:

1. Y to węzeł usuwany (fizycznie) w konwencji żądania usunięcia wskazanej wartości.

2. X to węzel, który zastępuje Y.

3. P to przodek węzła Y.

4. S to sąsiad (brat) węzła X.

Będziemy rozpatrywali cztery następujące przypadki, że:

1. S będzie koloru czerwonego.

2. S będzie koloru czarnego, oraz będzie miał obydwa nastepniki czarne.

3. S będzie koloru czarnego, oraz prawy następnik będzie czarny, a lewy - czerwony.

4. S będize koloru czarnego, a jego prawy następnik - koloru czerwonego.

Oto graficzna ilustracja tych przypadków:

Należy tu pamiętać o tym, że usunięcie węzła czerwonego w żaden sposób nie wpłynie na zmianę własności drzewa red black. Dodatkowo funkcja korekty jest wywoływana dla węzła z nadmiarowym kolorem czarnym (jest to zawsze jeden z nastepników fizycznie usuwanego węzła). Inaczej powyższe przypadki wyglądają mniej więcej tak:

I teraz zobaczmy, jak wygląda zmiana w przypadku pierwszym. Wykonamy tu rotację S wokół P i przekolorowanie S i P:

Kolejny z przypadków, czyli drugi. Tu nastąpi przekolorowanie S na czerwono, jeżeli P jest koloru czarnego, to nie dokonujemy zmian, natomiast, gdy P jest czerwone, to zmieniamy na czarny, jak poniżej:

Trzeci przypadek. Nastapi tu rotacja lewego potomka S wokół S, oraz zmiana kolorów S i lewego potomka S:

I ostatni, czwarty. Tutaj mamy rotację S wokół P, oraz przekolorowanie S na czerwono i prawego następnika S oraz P na czarno.

Teraz odnieśmy się do konkretnych przykładów usunięć. Oto przykład dla przypadku drugiego:

Dla przypadku pierwszego:

I dla przypadku trzeciego:

Teraz jeszcze omówmy przypadek usunięcia węzła z wartością 11. Będziemy tu mieli do czynienia z przypadkiem drugim. Oto jak wyglada

Własnie z górnego drzewka mamy usunąć węzeł z wartością 11. Drugi rysunek ilustruje drzewko po usunięciu węzła zgodnie z procedurą drzewa BST, ale teraz musimy wykonać dodatkowe modyfikacje według tego, o czym wczesniej mówilismy, czyli:

---