« poprzedni punkt   następny punkt »


4. Usuwanie z drzewa AVL.

Zasada usuwania elementu z drzewa AVL,

delete : Et ´ AVL ® AVL,

jest prawie taka sama, jak dla drzew binarnych poszukiwań. Jednak, podobnie jak w przypadku wstawiania elementu, wynikiem zastosowania procedury delete, opisanej dla drzew binarnych poszukiwań, nie zawsze otrzymane drzewo jest wyważone.  Postępowania będzie więc nieco bardziej skomplikowana niż dla drzew BST.

Metoda

  1. Znajdź wierzchołek z etykietą, którą chcesz usunąć z drzewa (o ile znajduje się ona w drzewie),
  2. Usuń tę etykietę stosując algorytm delete dla BST,
  3. Wylicz wagi wierzchołków na ścieżce od usuniętego wierzchołka w kierunku korzenia drzewa,
  4. Wykonaj rotację względem każdego napotkanego wierzchołka, którego waga wynosi +2 lub -2.

Zauważmy, że faktycznie usuwany wierzchołek, o którym mowa w punkcie 3 opisanej metody, nie zawsze jest tym wierzchołkiem, którego etykietę usuwamy (por. algorytm delete dla BST, przypadek, gdy wierzchołek z usuwaną etykietą ma dwa następniki).

Przykład 4.1

Rozważmy przykład przedstawiony na rysunku 8.9(a). Usunięcie etykiety 1 spowoduje odwiązanie węzła z tą etykietą, bo jest on liściem w tym drzewie. Wynikiem usunięcia 1 jest drzewo przedstawione na rysunku 8.9(b). Poza wierzchołkiem z etykietą 2, nie zmieniły się żadne dowiązania, ani wagi wierzchołków.

Jeśli teraz usuniemy z drzewa (rysunek 8.9(b)) etykietę korzenia, to sytuacja jest dużo bardziej skomplikowana. Przede wszystkim nie usuwamy bezpośrednio wierzchołka z etykietą 10, ale jego bezpośredni następnik (tzn. najmniejszy element w jego prawym poddrzewie), wierzchołek z etykietą 11. Etykieta 11 znajdzie się teraz w korzeniu drzewa wynikowego. Otrzymane drzewo jest drzewem binarnych poszukiwań, nie jest jednak drzewem AVL (por. rysunek 8.9(d)).

Zgodnie z punktem 3 opisanej metody modyfikujemy wagi (o ile to potrzebne) wierzchołków cofając się wzdłuż ścieżki poszukiwań. Ponieważ wierzchołek z etykietą 12, który obejrzymy jako pierwszy, ma teraz wagę -2, należy wykonać rotację prostą w lewo. Wynik tej rotacji jest przedstawiony na rysunku 8.9 (d). Jednak otrzymane drzewo binarnych poszukiwań nie jest wyważone, o czym się przekonamy wyliczając wagę korzenia drzewa: rotacja spowodowała zmniejszenie wysokości prawego poddrzewa, które już wcześniej miało mniejszą wysokość. Zgodnie z punktem 4 musimy kontynuować wykonywanie rotacji, tym razem względem korzenia drzewa (wierzchołek z etykietą 11). Wynik rotacji jest przedstawiony na rysunku 8.9 (e). J

 

Zwróćmy jeszcze raz uwagę na istotną różnice w procesie wyważania drzewa dla operacji insert i dla operacji delete. O ile w przypadku wstawiania nowego elementu, zawsze wystarczy co najwyżej jedna rotacja, to nie jest tak w przypadku usuwania. Usunięcie etykiety 10, w przykładzie 4.1, zmusiło nas do wykonania dwóch rotacji. A jak jest w przypadku ogólnym? Jaka może być liczba niezbędnych rotacji, jeśli drzewo ma n elementów?

Rozważmy drzewo D1 = <LD1,B,PD1> i niech waga wierzchołka B wynosi -1, tzn. prawe poddrzewo, oznaczone tu przez PD1, jest wyższe niż lewe poddrzewo. Załóżmy teraz, że usunięcie jakiegoś elementu  x spowodowało zmniejszenie wysokości poddrzewa LD1. Zatem, dla odzyskania równowagi, konieczna będzie rotacja w lewo (prosta lub podwójna) względem korzenia B. Wykonanie tej rotacji może spowodować zmniejszenie się wysokości drzewa D1. Niech teraz D1, będzie prawym poddrzewem pewnego drzewa D2 = <LD2,A,D1> o korzeniu A i lewym poddrzewie LD2, którego wysokość była o jeden większa niż wysokość drzewa D1. Wynika stąd, że waga w wierzchołku A zmieniła się z +1 na +2. Wymagana jest więc rotacja względem wierzchołka A.  Ta rotacja mogła zmniejszyć wysokość drzewa D2. Kontynuując, możemy sobie wyobrazić, że drzewo D2  jest lewym poddrzewem pewnego drzewa D3 = <D2, C, PD3>, którego prawe poddrzewo  PD3 było na początku o 1 wyższe niż drzewo D2. W wyniku zmiany wysokości w obrębie drzewa D2, waga w korzeniu drzewa D3 zmieni się z -1 na -2, a więc konieczna będzie rotacja względem tego wierzchołka, itd. Z tych rozważań wynika, że w najgorszym przypadku jedno usunięcie etykiety może spowodować "lawinę" kolejnych  rotacji dla wszystkich wierzchołków wzdłuż jednej ścieżki, od usuniętego wierzchołka do korzenia. Liczba rotacji może więc być oszacowana przez O(lgn), dla drzewa o n wierzchołkach.

Pytanie 4: Co będzie etykietą korzenia drzewa AVL, jeśli zostało ono utworzone przez kolejne wstawianie, do początkowo pustego drzewa, elementów 1,2,3,4,5,6,7,8,9,0, a następnie usunięcie etykiety, która znalazła się w korzeniu drzewa?


« poprzedni punkt   następny punkt »