W teoretycznej informatyki , AVL drzew były historycznie pierwszy automatycznie zrównoważone binarne drzewa badawcze . W drzewie AVL wysokości dwóch poddrzew tego samego węzła różnią się najwyżej o jeden. Znajdowanie, wstawianie i usuwanie to najgorsze scenariusze. Wstawianie i usuwanie wymaga rotacji .
Nazwa „Drzewo AVL” pochodzi od odpowiednich imion jego dwóch wynalazców, Georgii Adelson-Velsky (en) i Evguenii Landis (en) , którzy opublikowali je w 1962 roku pod tytułem „Algorytm organizacji informacji” .
Współczynnik równowagi węzła to różnica między wysokością jego prawego poddrzewa a wysokością jego lewego poddrzewa. Węzeł ze współczynnikiem równowagi równym 1, 0 lub -1 jest uważany za zrównoważony. Węzeł z dowolnym innym czynnikiem jest uważany za niezrównoważony i wymaga ponownego zrównoważenia. Współczynnik równoważenia jest albo obliczany z odpowiednich wysokości poddrzew, albo przechowywany w każdym węźle drzewa (co oszczędza miejsce, współczynnik ten może być przechowywany na dwóch bitach, ale komplikuje operacje wstawiania i usuwania).
Podstawowe operacje drzewa AVL na ogół implementują te same algorytmy, co w przypadku drzewa wyszukiwania binarnego , z tym wyjątkiem, że konieczne jest dodanie rotacji równoważących zwane „obrotami AVL”.
Wstawianie węzła do drzewa AVL odbywa się w dwóch etapach: po pierwsze, węzeł jest wstawiany dokładnie w taki sam sposób, jak w drzewie wyszukiwania binarnego ; następnie wracamy do korzenia z wstawionego węzła, korygując współczynniki równoważące, jeśli różnica wysokości jest ≤ 1, lub wykonując pojedynczy lub podwójny obrót (= 2 powiązane pojedyncze obroty), jeśli różnica wysokości jest większa niż 1 Wysokość h wału jest w , a obroty przy stałym koszcie, wstawienie jest ostatecznie wykonane w .
Przy każdym wstawieniu konieczne będzie wykonanie 0 lub 1 pojedynczego lub podwójnego obrotu.
Usunięcie w drzewie AVL może być wykonane przez kolejne rotacje usuwanego węzła aż do liścia (dostosowując współczynniki równoważące lub, jeśli nie jest to możliwe, wybierając te rotacje, aby drzewo pozostało zrównoważone), a następnie usuwanie tego arkusza bezpośrednio. Usuwanie odbywa się również w .
Dla każdego usunięcia konieczne będzie przejście od 0 do h rotacji, gdzie h jest wysokością drzewa.
Wyszukiwanie w drzewie AVL działa dokładnie tak samo, jak w przypadku drzewa wyszukiwania binarnego , a ponieważ wysokość drzewa AVL wynosi , jest wykonywane w . W przeciwieństwie do tego, co dzieje się z drzewami splay , badania nie zmieniają struktury drzewa.
W drzewie AVL o wysokości h , w najgorszym przypadku, zakładając, że drzewo jest niezrównoważone po lewej stronie, lewe poddrzewo będzie miało wysokość h -1, podczas gdy prawe poddrzewo będzie miało wysokość h -2. formuła przez indukcję, aby poznać minimalną wielkość drzewa AVL o wysokości h . Ta formuła rekurencyjna jest zbliżona do rekurencyjnej definicji liczb Fibonacciego : . Jeżeli asymptotyczne oszacowanie od gdzie jest numer złoty .
Ze względu na właściwość równowagi poddrzew AVL, maksymalna wysokość AVL z wewnętrznymi węzłami jest powiązana z minimalną wielkością wysokości AVL . Maksymalna wysokość jest mniejsza niż .
Daje to wzór na obliczenie wysokości, w najgorszym przypadku, dla drzewa AVL zawierającego n wewnętrznych węzłów.
Ten rozmiar jest lepszy niż w przypadku drzew czerwonych i czarnych , których mamy .