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+1−1
Niech się Fibonacciego drzewa o wysokości ; ma węzeł. [ 1 , 2 , TAoCP 3 ]ShhFh+2−1
Teraz pozwólmy z sekwencją drzew, które uważamy za kontrprzykład.(Th)i≥1Th=N(Sh,Ch)
Rozważ wartość równoważenia masy pierwiastka dla jakiegoś :Thh∈N+
Fh+22h+1+Fh+2−1=11+2h+1Fh+2−1Fh+2∼Fh+22h+1=15√(ϕh+2−ϕ^h+2)2h+1∼ϕh+25–√⋅2h+1→h→∞0
To kończy dowód.
Notacja :
- Fn jest tą liczbą Fibonacciegon
- ϕ≈1.6 to złoty współczynnik , jego koniugat.ϕ^≈−0.62
- f∼g oznacza, że i są asymptotycznie równe, tj. .fglimn→∞f(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:hh−1h−2
[ źródło ]
Ustawiliśmy powtarzalność dla liczby węzłów w tak skonstruowanym drzewie o wysokości :f(h)h
f(1)f(2)f(h)=1=2=f(h−1)+f(h−2)+1n≥3
Jego rozwiązanie prowadzi do którego użyliśmy powyżej.f(h)=Fh+2−1
Ten sam dowód podano (mniej szczegółowo) w drzewach wyszukiwania binarnego o ograniczonej równowadze autorstwa Nievergelt i Reingold (1972).