Drzewo AVL
Z Wikipedii
Drzewo AVL, nazywane również drzewem dopuszczalnym, to zrównoważone binarne drzewo poszukiwań (BST), w którym wysokość lewego i prawego poddrzewa każdego węzła różni się co najwyżej o jeden. Nazwa AVL pochodzi od nazwisk rosyjskich matematyków: Adelsona-Velskii oraz Landisa (właściwie: Gieorgij Adelson-Wielskij i Jewgienij Ładnis), którzy zaproponowali rozwiązanie problemu utrzymania dobrego drzewa wyszukiwań w roku 1962 [1].
Drzewo AVL pozostaje drzewem BST, co oznacza, że wierzchołki są uporządkowane w określony sposób. Zazwyczaj przyjmuje się, iż elementy w lewym poddrzewie są mniejsze od wierzchołka, zaś w prawym - większe. Zrównoważenie drzewa osiąga się przypisując każdemu węzłowi współczynnik wyważenia, który jest równy różnicy wysokości lewego i prawego poddrzewa. Może wynosić 0, +1 lub -1. Wstawiając lub usuwając elementy drzewa (tak aby zachować własności drzewa BST) modyfikuje się też współczynnik wyważenia, a gdy przyjmie on niedozwoloną wartość wykonuje specjalną operację rotacji węzłów, która przywraca zrównoważenie.
Koszt modyfikacji drzewa jest nieco większy niż dla zwykłego drzewa BST, ale za to własności drzewa AVL gwarantują, że pesymistyczny czas wyszukiwania elementu w drzewie o n węzłach wynosi 1.44(log2n), podczas gdy dla niezrównoważonego BST (w postaci listy) czas ten wynosi n.
Drzewa AVL są często porównywane z czerwono-czarnymi drzewami, ponieważ pozwalają na wykonanie tych samych operacji (dodawanie, usuwanie oraz wyszukiwanie elementów) o równej co do rzędu pesymistycznej złożoności czasowej O(log n). Przy powtarzających się wyszukiwaniach drzewa AVL są jednak wydajniejsze. [2]
W wielu praktycznych zastosowaniach zdarza się, że do części obiektów sięga się częściej niż do pozostałych, przykładem może być słownik. Wówczas lepszym rozwiązaniem jest zastosowanie optymalnego drzewa poszukiwań.
Podobnie jak w BST, nie jest możliwe, by drzewo posiadało dwa równe elementy. Zazwyczaj oznacza to, iż elementy muszą posiadać unikalny klucz identyfikacyjny; problem polega na tym, że drzewa z równymi elementami - nawet po zmodyfikowaniu porządku dzielącego elementy do lewych i prawych poddrzew - nie da się później zrównoważyć. Problem ten można rozwiązać na przykład przez przechowywanie w węzłach drzewa list zawierających elementy o identycznych kluczach.
Spis treści |
[edytuj] Operacje
Algorytmy podstawowych operacji na drzewie AVL przypominają te z binarnych drzew poszukiwań, ale są poprzedzane lub następują po nich jedna lub więcej "rotacji". Wszystkie algorytmy są zazwyczaj realizowane poprzez rekurencję. Koszt każdej operacji to O(log n).
[edytuj] Wstawianie
Wstawianie do drzewa AVL może odbywać się tak, jak gdyby było ono zwyczajnym drzewem poszukiwań binarnych, następnie zaś, odtwarzając kroki w kierunku korzenia, wykonywane są aktualizacje wyważeń węzłów. Zmiana wartości współczynnika wyważenia na 0 oznacza, iż wysokość poddrzew nie została zmieniona. Operacja wstawiania jest wówczas zakończona. Zmiana współczynnika wyważenia na 1 lub -1 oznacza, iż poddrzewo, którego korzeniem jest rozważany wierzchołek, zachowało własność drzewa AVL, lecz jego wysokość uległa zwiększeniu. Informacja o tym przekazywana jest do ojca tego węzła.
Jeśli współczynnik został zmieniony na 2 lub -2, to drzewo straciło własność AVL. Aby ją przywrócić, potrzebna jest rotacja. Rotacja drzewa będzie zawsze zostawiać poddrzewo zrównoważone, nie ma potrzeby wykonywania dalszych aktualizacji.
[edytuj] Usuwanie
Jeśli usuwany węzeł jest liściem, zostaje usunięty. Jeśli nie jest liściem, musi zostać zastąpiony największym elementem z jego lewego poddrzewa lub najmniejszym z jego prawego poddrzewa. Wyszukany największy lub najmniejszy element ma co najwyżej jedno dziecko. Po jego usunięciu odtwarzana jest ścieżka do korzenia, zaś współczynniki wyważenia są aktualizowane. Odtwarzanie może być zatrzymane, jeśli współczynnik wyważenia zostaje zmieniony na -1 lub 1, oznacza to bowiem, iż wysokość poddrzewa pozostaje niezmieniona. Zmiana współczynnika wyważenia na 0 oznacza zmniejszenie wysokości poddrzewa, aktualizowanie współczynników musi być kontynuowane. Jeśli współczynnik zostanie zmieniony na -2 lub 2, to wykonywana jest rotacja w celu przywrócenia struktury AVL. W przeciwieństwie do operacji wstawiania, wystąpienie rotacji nie musi oznaczać, iż drzewo zostało wyważone. W pesymistycznym przypadku rotacje będą wykonywane aż do wierzchołka drzewa.
[edytuj] Wyszukiwanie
Wyszukiwanie w drzewie AVL jest wykonywane tak samo jak w niezrównoważonym drzewie BST, dzięki serii porównań wartości wyszukiwanej z wierzchołkami poczynając od korzenia. Wynik porównania oraz istnienie poddrzew pozwala stwierdzić, czy element szukany jest wierzchołkiem, znajduje się w lewym bądź prawym poddrzewie, czy też nie należy do drzewa. Zachowanie struktury AVL pozwala jednak na redukcję pesymistycznego czasu wyszukiwania do O(lg n).
Operacja wyszukiwania nie modyfikuje struktury drzewa, więc nigdy nie pociąga wyważania drzewa (rotacji węzłów).
[edytuj] Zobacz też
[edytuj] Linki zewnętrzne
Przypisy
- ↑ Donald Knuth, Sztuka programowania. Tom 3. Sortowanie i wyszukiwanie, Wydawnictwa Naukowo-Techniczne, Warszawa 2002
- ↑ Pfaff, Ben (czerwiec 2004). Performance Analysis of BSTs in System Software (PDF). Stanford University.
