Drzewa AVL nie są zrównoważone pod względem masy?

22

W poprzednim pytaniu była definicja drzew zrównoważonych pod względem masy i pytanie dotyczące drzew czerwono-czarnych.

To pytanie dotyczy tego samego pytania, ale dotyczy drzew AVL .

Pytanie brzmi, biorąc pod uwagę definicję drzew zrównoważonych jak w drugim pytaniu,μ

Czy jest jakieś takie, że wszystkie wystarczająco duże drzewa AVL są zrównoważone ?μ>0μ

Zakładam, że istnieje tylko jedna definicja drzew AVL i nie ma dwuznaczności.

Aryabhata
źródło

Odpowiedzi:

18

Twierdzenie : Nie, nie ma takiego .μ

Dowód : podajemy nieskończoną sekwencję rosnących rozmiarów drzew AVL, których wartość bilansu masy wynosi , co jest sprzeczne z twierdzeniem.0

Niech pełne drzewo wysokości ; ma węzłów.Chh2h+11

Niech się Fibonacciego drzewa o wysokości ; ma węzeł. [ 1 , 2 , TAoCP 3 ]ShhFh+21

Teraz pozwólmy z sekwencją drzew, które uważamy za kontrprzykład.(Th)i1Th=N(Sh,Ch)

Rozważ wartość równoważenia masy pierwiastka dla jakiegoś :ThhN+

Fh+22h+1+Fh+21=11+2h+1Fh+21Fh+2Fh+22h+1=15(ϕh+2ϕ^h+2)2h+1ϕh+252h+1h0

To kończy dowód.

Notacja :

  • Fn jest tą liczbą Fibonacciegon
  • ϕ1.6 to złoty współczynnik , jego koniugat.ϕ^0.62
  • fg oznacza, że i są asymptotycznie równe, tj. .fglimnf(n)g(n)=1

Uwaga : Drzewa Fibonacciego są dokładnie tymi drzewami AVL z najmniejszymi węzłami dla danej wysokości (lub równoważnie maksymalną wysokością dla danej liczby węzłów).

Dodatek : Jak możemy wymyślić drzewa Fibonacciego, jeśli nie słyszeliśmy o nich profesora? Cóż, jak wyglądałoby drzewo AVL o wysokości z jak najmniejszą liczbą węzłów? Z pewnością potrzebujesz roota. Jedno z poddrzewa musi mieć wysokość i musimy wybrać go z możliwie najmniejszą liczbą węzłów. Drugi może mieć wysokość bez naruszenia warunków równoważenia wysokości, a my wybieramy ją również z możliwie najmniejszą liczbą węzłów. Zasadniczo konstruujemy drzewa, które chcemy rekurencyjnie! Oto cztery pierwsze:hh1h2

Pierwsze cztery drzewa Fibonacciego
[ źródło ]

Ustawiliśmy powtarzalność dla liczby węzłów w tak skonstruowanym drzewie o wysokości :f(h)h

f(1)=1f(2)=2f(h)=f(h1)+f(h2)+1n3

Jego rozwiązanie prowadzi do którego użyliśmy powyżej.f(h)=Fh+21


Ten sam dowód podano (mniej szczegółowo) w drzewach wyszukiwania binarnego o ograniczonej równowadze autorstwa Nievergelt i Reingold (1972).

Raphael
źródło