Drzewo AVL zostało wynalezione przez GM Adelsona - Velsky'ego i EM Landisa w 1962 roku. Drzewo zostało nazwane AVL na cześć jego wynalazców.
Drzewo AVL można zdefiniować jako drzewo poszukiwań binarnych o zrównoważonej wysokości, w którym każdy węzeł jest powiązany ze współczynnikiem równowagi obliczanym poprzez odjęcie wysokości jego prawego poddrzewa od wysokości lewego poddrzewa.
Mówi się, że drzewo jest zrównoważone, jeśli współczynnik równowagi każdego węzła mieści się w przedziale od -1 do 1, w przeciwnym razie drzewo będzie niezrównoważone i będzie wymagało zrównoważenia.
Współczynnik równowagi (k) = wysokość (po lewej (k)) - wysokość (po prawej (k))
Jeśli współczynnik równowagi dowolnego węzła wynosi 1, oznacza to, że lewe poddrzewo jest o jeden poziom wyższe od prawego poddrzewa.
Jeśli współczynnik równowagi dowolnego węzła wynosi 0, oznacza to, że lewe i prawe poddrzewo mają taką samą wysokość.
Jeśli współczynnik równowagi dowolnego węzła wynosi -1, oznacza to, że lewe poddrzewo jest o jeden poziom niżej niż prawe poddrzewo.
Drzewo AVL przedstawiono na poniższym rysunku. Widzimy, że współczynnik równowagi powiązany z każdym węzłem mieści się w przedziale od -1 do +1. dlatego jest to przykład drzewa AVL.
Złożoność
| Algorytm | Przeciętny przypadek | Najgorszy przypadek |
|---|---|---|
| Przestrzeń | NA) | NA) |
| Szukaj | o(log n) | o(log n) |
| Wstawić | o(log n) | o(log n) |
| Usuwać | o(log n) | o(log n) |
Operacje na drzewie AVL
Z uwagi na to, że drzewo AVL jest również drzewem poszukiwań binarnych, wszelkie operacje wykonywane są w taki sam sposób, jak w drzewie poszukiwań binarnych. Wyszukiwanie i przechodzenie nie prowadzi do naruszenia właściwości drzewa AVL. Jednakże wstawianie i usuwanie to operacje, które mogą naruszyć tę właściwość i dlatego należy je ponownie przejrzeć.
| SN | Operacja | Opis |
|---|---|---|
| 1 | Wprowadzenie | Wstawienie do drzewa AVL odbywa się w taki sam sposób jak w drzewie wyszukiwania binarnego. Może to jednak prowadzić do naruszenia właściwości drzewa AVL i dlatego drzewo może wymagać zrównoważenia. Drzewo można zrównoważyć stosując rotacje. |
| 2 | Usunięcie | Usunięcia można także dokonać analogicznie jak w drzewie wyszukiwania binarnego. Usunięcie może również zaburzyć równowagę drzewa, dlatego w celu przywrócenia równowagi drzewa stosuje się różnego rodzaju rotacje. |
Dlaczego drzewo AVL?
Drzewo AVL kontroluje wysokość drzewa wyszukiwania binarnego, nie pozwalając na jego przekrzywienie. Czas potrzebny na wszystkie operacje w drzewie poszukiwań binarnych o wysokości h wynosi Oh) . Można go jednak rozszerzyć na NA) jeśli BST zostanie przekrzywiony (tj. najgorszy przypadek). Ograniczając tę wysokość do log n, drzewo AVL nakłada górną granicę na każdą operację O(log n) gdzie n jest liczbą węzłów.
Rotacje AVL
Rotację w drzewie AVL wykonujemy tylko w przypadku, gdy współczynnik równowagi jest inny -1, 0 i 1 . Zasadniczo istnieją cztery rodzaje rotacji, które są następujące:
- Obrót L L: Wstawiony węzeł znajduje się w lewym poddrzewie lewego poddrzewa A
- R R obrót: Wstawiony węzeł znajduje się w prawym poddrzewie prawego poddrzewa A
- Obrót LR: Wstawiony węzeł znajduje się w prawym poddrzewie lewego poddrzewa A
- Obrót R L: Wstawiony węzeł znajduje się w lewym poddrzewie prawego poddrzewa A
Gdzie węzeł A jest węzłem, którego współczynnik równowagi jest inny niż -1, 0, 1.
Pierwsze dwa obroty LL i RR to pojedyncze obroty, a kolejne dwa obroty LR i RL to podwójne obroty. Aby drzewo było niezrównoważone minimalna wysokość musi wynosić co najmniej 2. Rozumiemy każdy obrót
1. Obrót RR
Kiedy BST staje się niezrównoważony w wyniku wstawienia węzła do prawego poddrzewa prawego poddrzewa A, wówczas wykonujemy rotację RR, rotacja RR jest obrotem w kierunku przeciwnym do ruchu wskazówek zegara, który jest stosowany na krawędzi poniżej węzła o współczynniku równowagi -2
W powyższym przykładzie węzeł A ma współczynnik równowagi -2, ponieważ węzeł C jest wstawiony w prawym poddrzewie A prawego poddrzewa. Obrót RR wykonujemy na krawędzi poniżej A.
2. Rotacja LL
Kiedy BST staje się niezrównoważony w wyniku wstawienia węzła do lewego poddrzewa lewego poddrzewa C, wówczas wykonujemy obrót LL, obrót LL jest obrotem zgodnym z ruchem wskazówek zegara, który jest stosowany na krawędzi poniżej węzła o współczynniku równowagi 2.
W powyższym przykładzie węzeł C ma współczynnik równowagi 2, ponieważ węzeł A jest wstawiony do lewego poddrzewa C lewego poddrzewa. Wykonujemy obrót LL na krawędzi poniżej A.
3. Obrót LR
Podwójne rotacje są nieco trudniejsze niż pojedyncze rotacje, co wyjaśniono już powyżej. rotacja LR = rotacja RR + rotacja LL, czyli najpierw rotacja RR wykonywana jest na poddrzewie, a następnie rotacja LL na pełnym drzewie, przez pełne drzewo rozumiemy pierwszy węzeł ze ścieżki wstawianego węzła, którego współczynnik równowagi jest inny niż -1 , 0 lub 1.
Rozumiemy każdy krok bardzo wyraźnie:
listnode java
| Państwo | Działanie |
|---|---|
 | Węzeł B został wstawiony do prawego poddrzewa A, do lewego poddrzewa C, przez co C stał się węzłem niezrównoważonym o współczynniku równowagi 2. W tym przypadku mamy do czynienia z rotacją LR, gdzie: Wstawiony węzeł znajduje się w prawym poddrzewie lewego poddrzewa C |
 | Ponieważ obrót LR = RR + obrót LL, stąd RR (w kierunku przeciwnym do ruchu wskazówek zegara) na poddrzewie zakorzenionym w A jest wykonywany jako pierwszy. Wykonując obrót RR, node A , stało się lewym poddrzewem B . |
 | Po wykonaniu rotacji RR węzeł C jest nadal niezrównoważony, tj. ma współczynnik równowagi 2, ponieważ wstawiony węzeł A znajduje się po lewej stronie od C |
 | Teraz wykonujemy obrót LL zgodnie z ruchem wskazówek zegara na pełnym drzewie, czyli na węźle C. węzeł C stało się teraz prawym poddrzewem węzła B, A jest lewym poddrzewem B |
 | Współczynnik równowagi każdego węzła wynosi teraz -1, 0 lub 1, co oznacza, że BST jest teraz zrównoważony. |
4. Obrót RL
Jak już wspomniano, podwójne rotacje są nieco trudniejsze niż pojedyncze rotacje, co już wyjaśniono powyżej. R L rotacja = rotacja LL + rotacja RR, czyli najpierw wykonywana jest rotacja LL na poddrzewie, a następnie rotacja RR na pełnym drzewie, przez pełne drzewo rozumiemy pierwszy węzeł ze ścieżki wstawianego węzła, którego współczynnik równowagi jest inny niż -1 , 0 lub 1.
| Państwo | Działanie |
|---|---|
 | Węzeł B został wstawiony do lewego poddrzewa C prawe poddrzewo A , przez co A stał się węzłem niezrównoważonym o współczynniku równowagi - 2. Tym przypadkiem jest rotacja RL gdzie: Wstawiony węzeł znajduje się w lewym poddrzewie prawego poddrzewa A |
 | Ponieważ obrót RL = obrót LL + obrót RR, stąd LL (zgodnie z ruchem wskazówek zegara) na poddrzewie z korzeniami C wykonywany jest jako pierwszy. Wykonując obrót RR, node C stało się prawym poddrzewem B . |
 | Po wykonaniu rotacji LL, node A jest nadal niezrównoważony, tj. ma współczynnik równowagi -2, co wynika z prawego poddrzewa węzła A z prawego poddrzewa. |
 | Teraz wykonujemy rotację RR (obrót w kierunku przeciwnym do ruchu wskazówek zegara) na pełnym drzewie, czyli na węźle A. węźle C stał się teraz prawym poddrzewem węzła B, a węzeł A stał się lewym poddrzewem węzła B. |
 | Współczynnik równowagi każdego węzła wynosi teraz -1, 0 lub 1, co oznacza, że BST jest teraz zrównoważony. |
P: Skonstruuj drzewo AVL zawierające następujące elementy
H, I, J, B, A, E, C, F, D, G, K, L
1. Wstaw H, I, J
Po wstawieniu powyższych elementów, zwłaszcza w przypadku H, BST staje się niezrównoważony, ponieważ współczynnik równowagi H wynosi -2. Ponieważ BST jest przesunięty w prawo, wykonamy rotację RR w węźle H.
Wynikowe drzewo równowagi to:
2. Wstaw B, A
Po wstawieniu powyższych elementów, szczególnie w przypadku A, BST staje się niezrównoważony, ponieważ współczynnik równowagi H i I wynosi 2, bierzemy pod uwagę pierwszy węzeł z ostatniego wstawionego węzła, tj. H. Ponieważ BST z H jest przekrzywiony w lewo, wykonamy rotację LL na węźle H.
Wynikowe drzewo równowagi to:
3. Wstaw E
Po wstawieniu E, BST staje się niezrównoważone, ponieważ współczynnik równowagi I wynosi 2, ponieważ jeśli podróżujemy od E do I, okaże się, że jest on wstawiony do lewego poddrzewa prawego poddrzewa I, wykonamy obrót LR w węźle I. LR = RR + obrót LL
3 a) Najpierw wykonujemy rotację RR w węźle B
Powstałe drzewo po obrocie RR to:
3b) Najpierw wykonujemy rotację LL w węźle I
Wynikowe zrównoważone drzewo po rotacji LL to:
4. Wstaw C, F, D
Po wstawieniu C, F, D, BST staje się niezrównoważone, ponieważ współczynnik równowagi B i H wynosi -2, ponieważ jeśli podróżujemy z D do B, okaże się, że jest on wstawiony w prawym poddrzewie lewego poddrzewa B, wykonamy RL Obrót w węźle I. RL = LL + RR obrót.
4a) Najpierw wykonujemy rotację LL w węźle E
Powstałe drzewo po rotacji LL to:
4b) Następnie wykonujemy rotację RR w węźle B
Wynikowe zrównoważone drzewo po obrocie RR to:
5. Włóż G
Po wstawieniu G, BST staje się niezrównoważone, ponieważ współczynnik równowagi H wynosi 2, ponieważ jeśli podróżujemy z G do H, stwierdzimy, że jest on wstawiony do lewego poddrzewa prawego poddrzewa H, wykonamy rotację LR w węźle I. LR = RR + obrót LL.
svm
5 a) Najpierw wykonujemy rotację RR w węźle C
Powstałe drzewo po obrocie RR to:
5 b) Następnie wykonujemy rotację LL w węźle H
Wynikowe zrównoważone drzewo po rotacji LL to:
6. Wstaw K
Po wstawieniu K, BST staje się niezrównoważone, ponieważ współczynnik równowagi I wynosi -2. Ponieważ BST jest przesunięty w prawo od I do K, dlatego wykonamy rotację RR w węźle I.
Wynikowe zrównoważone drzewo po obrocie RR to:
7. Wstaw L
Po wstawieniu drzewo L jest nadal zrównoważone, ponieważ współczynnik równowagi każdego węzła wynosi teraz -1, 0, +1. Zatem drzewo to jest drzewem zrównoważonym AVL
