« poprzedni punkt    następny punkt »


1. Drzewa wyważone

Podstawową wadą drzew binarnych poszukiwań był liniowy koszt operacji memebr, insert i delete w przypadku pesymistycznym. Związane to było z tym, że niektóre ścieżki drzewa mogły mieć długość dużo większą niż inne. Na przykład, gdy wkładamy do drzewa BST  k elementów uporządkowanych rosnąco, to jedna ze ścieżek prawego poddrzewa wydłuży się o k wierzchołków, powodując znaczne pogorszenie kosztów wyszukiwania. Adelson, Velskii, Landis zaproponowali strukturę danych, która ma wszystkie zalety drzew binarnych poszukiwań, a dodatkowo wszystkie ścieżki od korzenia drzewa do liści mają w tej strukturze podobną długość. Strukturę tę, od nazwisk autorów pomysłu, nazywa się w literaturze, strukturą AVL.

Niech h(D) oznacza wysokość drzewa D, a LD(v) i PD(v) lewe i prawe poddrzewo wierzchołka v. Przyjmujemy dodatkowo dla pustego drzewa D, h(D)=-1.

Definicja 1.1  Powiemy, ze drzewo binarne jest wyważone, jeżeli dla wszystkich jego wierzchołków wysokości jego lewego i prawego poddrzewa różnią się co najwyżej o 1. Funkcję W, przyporządkowującą każdemu wierzchołkowi v drzewa wartość W(v)= h(LD(v)) - h(PD(v)) nazywamy funkcją wag, a wartość W(v) nazywamy wagą wierzchołka v.

Bezpośrednio z powyższej definicji wynika, że  drzewo binarne jest wyważone, jeśli funkcja wag dla tego drzewa przypisuje wierzchołkom tylko wartości 0, 1, -1.

Przykład 8.1

Na rysunku 8.1 przedstawiono drzewo binarne  z wagami przypisanymi wierzchołkom. Wszystkie liście mają wagę równą 0. Wierzchołek A ma wagę równą +1, ponieważ lewe poddrzewo ma wysokość 2, a prawe poddrzewo wysokość 1. Podobnie dla wierzchołków B i C. Wierzchołek D ma wagę równą -1, ponieważ lewe poddrzewo jest puste a prawe poddrzewo składa się tylko z jednego wierzchołka E i w związku z tym jego wysokość wynosi 0.  Z analizy wartości wag wynika, że jest to drzewo wyważone. J

 

 

Definicja 1.2  Drzewem AVL  nazywamy wyważone drzewo binarnych poszukiwań.

Przykład 8.2

Drzewo na rysunku 8.1(a) nie jest drzewem binarnych poszukiwań, jeśli porządek liniowy, obowiązujący wśród etykiet tego drzewa, to porządek alfabetyczny. Drzewo przedstawione na rysunku 8.1(b) jest drzewem binarnych poszukiwań ze względu na porządek alfabetyczny etykiet, ale nie jest drzewem wyważonym. Zatem żadne z drzew na rysunkach 8.1 nie jest drzewem AVL. Natomiast drzewo na rysunku 8.1(c) jest wyważonym drzewem binarnych poszukiwań, jest więc drzewem AVL. J

Operacje na drzewie AVL są typowymi operacjami na zbiorach uporządkowanych (używamy tych samych nazw operacji, jak w przypadku drzew BST):


member: Et ´ AVL ® B0
min: AVL ® Et
insert: Et ´ AVL ® AVL
delete: Et ´ AVL ® AVL


Algorytmy operacji member i min są identyczne jak w przypadku drzew BST, gdyż ich wykonanie nie modyfikuje struktury drzewa. Pozostałe operacje wykonuje się podobnie jak na drzewach BST z tym, że w przypadku, gdy otrzymany rezultat nie jest drzewem AVL, wykonuje się dodatkowo wyważanie drzewa, tak aby wynik końcowy był drzewem AVL.  O zasadach wyważania będzie mowa w następnym punkcie tego wykładu.

Implementacja drzewa AVL wymaga informacji o wagach wierzchołków. Wygodnie jest w tym celu rozważać obiekty node wzbogacone o atrybut hv, którego wartością jest wysokość drzewa o korzeniu w rozważanym wierzchołku. W niektórych aplikacjach przydatna też jest  referencja father do bezpośredniego poprzednika danego wierzchołka, na ścieżce w kierunku korzenia drzewa.

class node{                    lub     class node{
    val : Et;                                  val : Et;
    hv : int;                                  hv : int;
    left, right : node;                      left, right, father : node;
}                                            }

Te dodatkowe informacje pozwolą wyliczyć szybko wagi wierzchołków i poruszać się po drzewie od liści w kierunku korzenia.

Pytanie 1: Z ilu wierzchołków składa się najmniejsze drzewo AVL o wysokości 3?


« poprzedni punkt   następny punkt »