Drzewo AVL

Drzewo AVL, nazywane również drzewem dopuszczalnym – 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. Skrót AVL pochodzi od nazwisk rosyjskich matematyków: Adelsona-Velskiego oraz Landisa (właściwie: Gieorgij Adelson-Wielski i Jewgienij Łandis), którzy zaproponowali rozwiązanie problemu utrzymania dobrego drzewa wyszukiwań w roku 1962^[1].

Drzewo AVL pozostaje drzewem binarnych poszukiwań, co oznacza, że wierzchołki są uporządkowane w określony sposób. Zazwyczaj przyjmuje się, że 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, by 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 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(log₂n), podczas gdy dla niezrównoważonego BST (w postaci listy) czas ten wynosi n.

Drzewa AVL są często porównywane z drzewami czerwono-czarnymi, ponieważ pozwalają na wykonanie tych samych operacji (dodawanie, usuwanie oraz wyszukiwanie elementów) przy 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ć unikatowy 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.

Operacje[edytuj | edytuj kod]

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". Algorytmy te mogą być realizowane poprzez rekurencję lub, co nawet prostsze, poprzez iteracyjne przechodzenie po krawędziach w górę lub w dół drzewa. Koszt każdej operacji to Ο(log n).

Wstawianie[edytuj | edytuj kod]

Wstawianie do drzewa AVL może odbywać się tak, jak gdyby było ono zwyczajnym drzewem poszukiwań binarnych, następnie zaś są odtwarzane kroki w kierunku korzenia i wykonywane aktualizacje wyważeń węzłów. Zmiana wartości współczynnika wyważenia na 0 oznacza, iż wysokość poddrzewa 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. Maksymalnie będą potrzebne dwie rotacje, po których nie ma potrzeby wykonywania dalszych aktualizacji.

Usuwanie[edytuj | edytuj kod]

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, które zostaje teraz dzieckiem rodzica wyszukanego elementu. Po jego usunięciu odtwarzana jest ścieżka od rodzica wyszukanego elementu 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 korzenia drzewa.

Wyszukiwanie[edytuj | edytuj kod]

Wyszukiwanie w drzewie AVL jest wykonywane tak samo jak w niezrównoważonym 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).