Operacja wstawiania elementu do drzewa AVL, etykietowanego elementami zbioru Et,

insert : AVL ´ Et ® AVL, 

może być zrealizowana tak jak dla drzew binarnych poszukiwań. Problem polega na tym, że nie zawsze otrzymujemy w wyniku drzewo wyważone. Metoda wstawiania elementu do drzewa AVL składa się więc z trzech etapów:

1. znalezienie wierzchołka, do którego można dołączyć nową etykietę (o ile nie było jej jeszcze w drzewie),
2. utworzenie nowego wierzchołka i dowiązanie go do drzewa w znalezionym (w punkcie 1) węźle, oraz
3. poprawienie wartości wag wierzchołków na ścieżce poszukiwania, od ojca nowo-wstawionego wierzchołka w kierunku korzenia drzewa,
4. wykonanie rotacji względem pierwszego napotkanego wierzchołka, którego waga wynosi +2 lub -2, o ile taki istnieje.

Przykład 3.1

Kolejne etapy tworzenia drzewa AVL z elementów 1,2,3,5,4 przedstawiono na rysunku 8.6(a) i 8.6(b).

Po dołączeniu etykiety 3, otrzymane drzewo nie jest drzewem AVL, ponieważ waga w korzeniu wynosi teraz -2.  Prosta rotacja w lewo pozwoli jednak zrównoważyć to drzewo, jak pokazano na rysunku 8.6 (a).  Wstawienie etykiety 5 do prawego poddrzewa powoduje zwiększenie wysokości całego drzewa,  ale wagi są nadal dopuszczalne (por. rysunek 8.6(b)). Nowy element 4 również zwiększa wysokość, ale teraz waga wierzchołka 3 nie jest odpowiednia, wynosi bowiem -2. Łatwo zauważyć, że prosta rotacja w lewo względem 3 nie poprawi sytuacji. Jednak zastosowanie rotacji podwójnej doprowadza drzewo do stanu wyważenia, por. ostatni z grafów na rysunku 8.6(b). J

Sformułujemy teraz ogólne zasady wyważania, gdy do drzewa AVL wstawiamy nowy element. Reguły postępowania zależą od tego jakie są aktualne wagi wierzchołków i gdzie zostanie dowiązany nowy wierzchołek.

Niech D będzie drzewem AVL, D = <LD, r, PD>, do którego wstawiamy etykietę e. Niech D' oznacza drzewo otrzymane w wyniku zastosowania algorytmu insert(e,D) dla drzew BST. Załóżmy, że nowy wierzchołek z etykietą e został dowiązany w lewym poddrzewie drzewa D i że spowodowało to zwiększenie wysokości drzewa LD, ale LD nadal pozostaje drzewem wyważonym. Wynika stąd, że przed wstawieniem nowego wierzchołka, waga w korzeniu drzewa LD musiała być równa 0. Zachodzą następujące przypadki:

1. Jeżeli waga w wierzchołku drzewa D wynosiła 0, to po dołączeniu e, wynosi 1. Otrzymane drzewo D' jest więc drzewem AVL, chociaż jego wysokość jest o 1 większa niż drzewa D.

2. Jeżeli waga w wierzchołku drzewa D wynosiła -1, to po dołączeniu e wynosi 0. Otrzymane drzewo jest wyważone, a jego wysokość jest taka sama jak drzewa D.

3. Jeżeli waga w wierzchołku drzewa D wynosiła +1, to po dołączeniu e wynosi +2. Zatem drzewo D' nie jest wyważone. Typ użytej rotacji zależy od tego, czy e zostało dołączone do lewego, czy do prawego poddrzewa drzewa LD.

3a. Element e  znajduje się w lewym poddrzewie drzewa LD. Waga korzenia drzewa LD zmieniła się z 0 na +1. Zastosowanie pojedynczej rotacji w prawo pozwoli wyważyć otrzymane drzewo. Na rysunku rysunek 8.7 (a) przedstawiono opisaną w tym przypadku sytuację przed i po wykonaniu wstawienia elementu e, a na rysunku 8.7(b) rezultat zastosowania prostej rotacji w prawo. Zauważmy, że wysokość otrzymanego drzewa jest taka sama jak wysokość danego drzewa przed wstawieniem elementu e.

3b. Element e został dołączony do prawego poddrzewa drzewa LD. Waga drzewa LD zmieniła się więc z 0 na -1. Otrzymane drzewo nie jest wyważone. Zastosowanie rotacji podwójnej w prawo pozwoli je jednak wyważyć. Sytuacja opisana w tym przypadku, jest przedstawiona na rysunku 8.8(a). Skreślone wagi odpowiadają stanowi drzewa przed wykonaniem dołączenia etykiety e. Wynik wyważania jest natomiast przedstawiony na rysunku 8.8(b). Jak poprzednio, zauważmy, że wysokość drzewa po wykonaniu rotacji jest taka sama jak wysokość drzewa D.

Analogicznie, jeżeli nowy wierzchołek z etykietą e został dowiązany w prawym poddrzewie drzewa D i spowodowało to zwiększenie wysokości drzewa PD, ale PD nadal pozostaje drzewem wyważonym. Wynika stąd, że przed wstawieniem nowego wierzchołka, waga w korzeniu drzewa PD musiała być równa 0. Zachodzą  trzy następujące przypadki:

1. Jeżeli waga w wierzchołku drzewa D wynosiła 0, to po dołączeniu e, wynosi -1. Otrzymane drzewo D' jest więc drzewem AVL, chociaż jego wysokość jest o 1 większa niż drzewa D.

2. Jeżeli waga w wierzchołku drzewa D wynosiła +1, to po dołączeniu e wynosi 0. Otrzymane drzewo jest wyważone, a jego wysokość jest taka sama jak drzewa D.

3. Jeżeli waga w wierzchołku drzewa D wynosiła -1, to po dołączeniu e wynosi -2. Zatem drzewo D' nie jest wyważone. Typ użytej rotacji zależy od tego, czy e zostało dołączone do prawego, czy do lewego poddrzewa drzewa PD. W pierwszym przypadku opisanym na rysunku 8.7(c) zastosujemy prostą  rotację w lewo, która wyważy drzewo (por. 8.7 (d)). W drugim przypadku, przedstawionym na rysunku 8.8(c) zastosujemy podwójną rotację w lewo. Otrzymany wynik jest przedstawiony na rysunku 8.8(d).

Pytanie 3:  Ile co najwyżej rotacji trzeba wykonać, jeśli do drzewa  AVL o n wierzchołkach dołączamy jeden element?

« poprzedni punkt

następny punkt »