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

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,$\mu$

Czy jest jakieś takie, że wszystkie wystarczająco duże drzewa AVL są zrównoważone ?$\mu \gt 0$$\mu$

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

Twierdzenie : Nie, nie ma takiego .$\mu$

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.$C_h$$h$$2^{h+1}-1$

Niech się Fibonacciego drzewa o wysokości ; ma węzeł. [ 1 , 2 , TAoCP 3 ]$S_h$$h$$F_{h+2} - 1$

Teraz pozwólmy z sekwencją drzew, które uważamy za kontrprzykład.$(T_h)_{i\geq 1}$$T_h = N(S_h,C_h)$

Rozważ wartość równoważenia masy pierwiastka dla jakiegoś :$T_h$$h \in \mathbb{N}_+$

$\qquad \displaystyle \begin{align*} \frac{F_{h+2}}{2^{h+1} + F_{h+2} - 1} &= \frac{1}{1 + \frac{2^{h+1}}{F_{h+2}} - \frac{1}{F_{h+2}{}}} \\ &\sim \frac{F_{h+2}}{2^{h+1}} \\ &= \frac{\frac{1}{\sqrt{5}}(\phi^{h+2} - \hat{\phi}^{h+2})}{2^{h+1}} \\ &\sim \frac{\phi^{h+2}}{\sqrt{5}\cdot 2^{h+1}} \underset{h \to \infty}{\to} 0 \end{align*}$

To kończy dowód.

Notacja :

• $F_n$ jest tą liczbą Fibonacciego$n$
• $\phi \approx 1.6$ to złoty współczynnik , jego koniugat.$\hat{\phi} \approx -0.62$
• $f \sim g$ oznacza, że i są asymptotycznie równe, tj. .$f$$g$$\lim_{n \to \infty} \frac{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:$h$$h-1$$h-2$

^{[ źródło ]}

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

$\qquad \displaystyle \begin{align*} f(1) &= 1 \\ f(2) &= 2 \\ f(h) &= f(h-1) + f(h-2) + 1 \qquad n \geq 3 \end{align*}$

Jego rozwiązanie prowadzi do którego użyliśmy powyżej.$f(h) = F_{h+2} - 1$

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