Drzewo AVL

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 . $O (\ log_ {2} (n))$

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).

Operacje

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”.

Wprowadzenie

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 . $O (\ log (n))$ $O (\ log (n))$

Przy każdym wstawieniu konieczne będzie wykonanie 0 lub 1 pojedynczego lub podwójnego obrotu.

Usunięcie

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 . $O (\ log (n))$

Dla każdego usunięcia konieczne będzie przejście od 0 do h rotacji, gdzie h jest wysokością drzewa.

Badania

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. $O (\ log (n))$ $O (\ log (n))$

Wysokość

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 . $S _ {\ tekst {min}} (h)$ $S _ {\ tekst {min}} (h) = S _ {\ tekst {min}} (h-1) + S _ {\ tekst {min}} (h-2) +1$ $S _ {\ tekst {min}} (h)$ $\ frac {1} {\ sqrt {5}} \ varphi ^ {h-2} -1,$ $\ varphi$

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ż . $H _ {{maks}}$ $nie$ $h$ $\ log_ \ varphi (\ sqrt 5 (n + 2)) - 2 = \ log_ \ varphi (2) \ cdot \ log_2 (\ sqrt 5 (n + 2)) - 2 \ około 1 {{,}} 44 \ log_2 (n + 2) - 0 {{,}} 328$

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 . $2 \ razy \ log_ {2} {n}$

Uwagi i referencje

(w) G. Adelson-Velskii i EM Landis, Algorytm organizacji informacji . Matematyka radziecka Dokłady , 3: 1259-1263, 1962.
Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest i Clifford Stein , Wprowadzenie do algorytmiki , Dunod ,2002[ szczegóły wydania ], załącznik B.
(w) Theodore Norvell, [PDF] " Zastosowanie: drzewa AVL i złoty podział " , Discrete Math. dla Inżynierii , Memorial University , 2004.
Aby uzyskać informacje na temat rozmiaru, możemy również odwiedzić stronę internetową (w) http://www.dyalog.dk/dfnsdws/n_avl.htm .

Źródła

Danièle Beauquier, Jean Berstel, Philippe Chrétienne: Elementy algorytmiki . Masson, 1992. ( ISBN 2-225-82704-4 ) Zobacz w szczególności rozdział 6 o „drzewkach i uporządkowanych zbiorach”.
(w), Donald Knuth : Sztuka programowania , tom 3: „ sortowania i wyszukiwania ” 3 e wydanie. Addison-Wesley, 1997. ( ISBN 0-201-89685-0 ) Patrz w szczególności strony 458 do 475 sekcji 6.2.3: „ Drzewa zrównoważone ”, wyrażenie, które oznacza drzewa AVL w Knuth.

Zobacz również

Powiązane artykuły

Link zewnętrzny

Jean-Jacques Levy, École polytechnique : kurs algorytmiczny.