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 .

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 .

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 .

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.

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 .

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 .

Uwagi i referencje

  1. (w) G. Adelson-Velskii i EM Landis, Algorytm organizacji informacji . Matematyka radziecka Dokłady , 3: 1259-1263, 1962.
  2. Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest i Clifford Stein , Wprowadzenie do algorytmiki , Dunod ,2002[ szczegóły wydania ], załącznik B.
  3. (w) Theodore Norvell, [PDF] Zastosowanie: drzewa AVL i złoty podział  " , Discrete Math. dla Inżynierii , Memorial University , 2004.
  4. 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

Zobacz również

Powiązane artykuły

Link zewnętrzny

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">