« poprzedni punkt | następny punkt » |
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.
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
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 » |