AVL-Bäume sind nicht gewichtsausgeglichen?

In einer früheren Frage gab es eine Definition von gewichtsausgeglichenen Bäumen und eine Frage zu rot-schwarzen Bäumen.

Diese Frage ist die gleiche Frage zu stellen, aber für AVL-Bäume .

Die Frage ist, angesichts der Definition von $\mu$ ausgeglichenen Bäumen wie in der anderen Frage,

Gibt es einige $\mu \gt 0$ so dass alle ausreichend großen AVL-Bäume $\mu$ ausgeglichen sind?

Ich gehe davon aus, dass es nur eine Definition von AVL-Bäumen gibt und es keine Mehrdeutigkeit gibt.

Behauptung : Nein, es gibt kein solches $\mu$ .

Beweis : Wir geben eine unendliche Folge von AVL-Bäumen wachsender Größe an, deren Gewichtsausgleichswert gegen tendiert $0$, was der Behauptung widerspricht.

Sei $C_h$ der vollständige Baum der Höhe $h$ ; es hat $2^{h+1}-1$ Knoten.

Sei $S_h$ der Fibonacci-Baum der Höhe $h$ ; es hat $F_{h+2} - 1$ Knoten. [ 1 , 2 , TAoCP 3 ]

Nun sei $(T_h)_{i\geq 1}$ mit $T_h = N(S_h,C_h)$ die Folge von Bäumen, die wir für ein Gegenbeispiel halten.

Betrachten Sie den Gewichtsausgleichswert der Wurzel von $T_h$ für einige $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*}$

Damit ist der Beweis abgeschlossen.

Notation :

• $F_n$$n$
• $\phi \approx 1.6$$\hat{\phi} \approx -0.62$
• $f \sim g$$f$$g$$\lim_{n \to \infty} \frac{f(n)}{g(n)} = 1$

Anmerkung : Fibonacci-Bäume sind genau die AVL-Bäume mit den geringsten Knoten für eine bestimmte Höhe (oder entsprechend der maximalen Höhe für eine bestimmte Anzahl von Knoten).

Nachtrag : Wie können wir zu Fibonacci-Bäumen kommen, wenn wir nicht gehört hätten, dass ein Professor sie erwähnt hat? Nun, wie würde ein AVL-Baum der Höhe mit möglichst wenigen Knoten aussehen? Natürlich brauchst du eine Wurzel. Einer der Teilbäume muss die Höhe , und wir müssen ihn mit möglichst wenigen Knoten auswählen. Die andere kann die Höhe ohne die Höhenausgleichsbedingung zu verletzen, und wir wählen sie auch mit so wenigen Knoten wie möglich. Im Wesentlichen konstruieren wir die Bäume, die wir rekursiv wollen! Dies sind die ersten vier:h - 1 h - $h$$h-1$$h-2$

^{[ Quelle ]}

Wir haben eine Wiederholung für die Anzahl der Knoten in dem so konstruierten Baum mit der Höhe :$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*}$

Das Lösen führt zu das wir oben verwendet haben.$f(h) = F_{h+2} - 1$

Der gleiche Beweis wird (mit weniger Details) in Binary Search Trees of Bounded Balance von Nievergelt und Reingold (1972) erbracht.