Fibonacci-Baum
# Fibonacci-Baum

Der Fibonacci-Baum ist Gegenstand der Graphentheorie, vor allem aber eine Datenstruktur in der Informatik. Er stellt einen Spezialfall des AVL-Baums dar, und zwar zu gegebener Höhe denjenigen AVL-Baum mit der kleinsten Anzahl Knoten. Der Name deutet an, dass Fibonacci-Bäume ähnlich den Fibonacci-Zahlen rekursiv definiert werden können.

Entfernt man einen beliebigen Knoten eines Fibonacci-Baums, so entsteht ab der dritten Stufe ein Baum, der nicht mehr Fibonacci-Baum ist. Im Beispiel unten ist er auch nicht mehr AVL-Baum, wenn z. B. eine 1, die nicht die linkeste ist, entfernt wird.

Eine Art „Basis des Logarithmus“ ist wie bei den Fibonacci-Zahlen die Zahl $\Phi :={\tfrac {1+{\sqrt {5}}}{2}}\approx 1{,}618034$ des goldenen Schnittes. Ideal wäre für einen Binärbaum natürlich die Basis $2$, das Aufrechterhalten schärferer Balancekriterien, z. B. der Höhenausgewogenheit beim vollständig balancierten Binärbaum, ist aber nach Modifikationen des Baums so aufwändig, dass im Mittel die Gesamtkosten solcher Bäume höher werden, es sei denn, die Anwendung ist ganz extrem vom Suchen dominiert. Das AVL-Kriterium erscheint als attraktiver Kompromiss.

Fibonacci-Bäume werden vor allem bei Effizienzüberlegungen zu höhen-balancierten Bäumen, insbesondere AVL-Bäumen, als Extremfälle und Vergleichsobjekte herangezogen.

## Rekursive Definition

Die rekursive Definition erfolgt in der Art:

* Der Fibonacci-Baum $F_{0}$ der Stufe 0 ist der leere Baum.
* Der Fibonacci-Baum $F_{1}$ der Stufe 1 ist ein Baum, der nur aus einem Knoten besteht.
* Ein Fibonacci-Baum $F_{h}$ der Stufe $h$ (mit $h\geq 2$) besteht aus einer Wurzel, deren linkes Kind ein Fibonacci-Baum der Stufe $h-1$ und deren rechtes Kind ein Fibonacci-Baum der Stufe $h-2$ ist.

## Eigenschaften

* Alle internen Knoten (Knoten, die nicht Blätter sind) haben den Balance-Faktor −1.
* Der Fibonacci-Baum $F_{h}$ der Stufe $h$ (mit $h\geq 0$) hat die Höhe $h$.
* Ist $n_{h}$ die Anzahl der Knoten des Fibonacci-Baums der Stufe $h$, dann gilt

    $n_{0}=0$
    $n_{1}=1$
    $n_{h}=1+n_{h-1}+n_{h-2}$ für $h\geq 2$
* Ist $b_{h}$ die Anzahl der Blattknoten des Fibonacci-Baums der Stufe $h$, dann gilt

    $b_{0}=0$
    $b_{1}=1$
    $b_{h}=b_{h-1}+b_{h-2}$ für $h\geq 2$
* Ist $e_{h}$ die Anzahl der Einfügepunkte (Halbblätter; 1 Blatt = 2 Halbblätter) des Fibonacci-Baums der Stufe $h$, dann gilt

    $e_{0}=1$
    $e_{1}=2$
    $e_{h}=e_{h-1}+e_{h-2}$ für $h\geq 2$
* Mit Hilfe der Bezeichnung $f_{h}$ für die $h$-te Fibonacci-Zahl lassen sich diese Größen auch so ausdrücken:

    $n_{h}=f_{h+2}-1$
    $b_{h}=f_{h}$
    $e_{h}=f_{h+2}=n_{h}+1$
    (Für jeden gerichteten Binärbaum gilt $e=n+1$.)
* Zu einer gegebenen Höhe entspricht ein Fibonacci-Baum einem AVL-Baum mit minimaler Knotenanzahl, er ist also am schlechtesten balanciert.
* Nach der Formel von Moivre-Binet ist die Anzahl der Knoten

       $n_{h}$$=f_{h+2}$$-1$ $={\tfrac {1}{\sqrt {5}}}{\biggl{\biggr .}$$\left({\tfrac {1+{\sqrt {5}}}{2}}\right)^{h+2}$$-{\biggl .}\left({\tfrac {1-{\sqrt {5}}}{2}}\right)^{h+2}{\biggr ]}$$-1$ $\geqq$${\tfrac {\Phi ^{h+2}}{\sqrt {5}}}$$-{\tfrac {(-\Phi ^{-1})^{4}}{\sqrt {5}}}$$-1$ für $h\geq 1$ und $\geqq$${\tfrac {\Phi ^{h+2}}{\sqrt {5}}}$$-2$ für $h\geq 0$.
* Damit lässt sich die Höhe $h$ in Abhängigkeit von der Knotenanzahl $n\geq 1$ abschätzen zu

       $h$ $\leqq c\log _{2}(n+d)+b$ $\leqq c\log _{2}(n+2)+b$
    mit $c:={\tfrac {1}{\log _{2}\Phi }}\approx 1{,}440420$ , $b:={\tfrac {c}{2}}\log _{2}5-2\approx -0{,}327724$ und $d:={\tfrac {1}{\Phi ^{4}{\sqrt {5}}}}+1\approx 1{,}065248$.

## Andere dünnste AVL-Bäume

Vertauscht man an einem Knoten das linke mit dem rechten Kind, entsteht wieder ein dünnster AVL-Baum. Damit ergibt sich für die Anzahl $a_{h}$ dünnster AVL-Bäume der Höhe $h$

    $a_0$ =1 $a_1$ =1 $a_h$ = $(a_{h–1}$ • $a_{h–2})$ • 2   (für h ≥ 2)   (h–1 links & h–2 rechts) + umgekehrt

Das ist in geschlossener Form $a_{h}=2^{f_{h+1}-1}$, welches sich für $h\to \infty$ der Funktion

    $2^{\Phi ^{h+f}-1}$

mit $f:=1-{\tfrac {\log _{\Phi }5}{2}}\approx -0{,}672276$ annähert.

Die Anzahl $A_{h}$ aller AVL-Bäume der Höhe $h$ lässt sich wie folgt berechnen:

    $A_0$ =1 $A_1$ =1 $A_h$ = $(A_{h–1}$ • $A_{h–2})$ • 2 + $(A_{h–1}$ • $A_{h–1})$ (für h ≥ 2)   (h–1 links & h–2 rechts) + umgekehrt + (h–1 links & h–1 rechts)

Es handelt sich um die Folge A029758 in OEIS, die sich für $h\to \infty$ der Funktion

    $k^{2^{h}}=2^{2^{h+K}}$

mit $k:=k_{\mathsf {A029758}}\approx 1{,}436873$ oder $K:=\log _{2}{\log _{2}{k}}\approx -0{,}935305$ annähert.

Beide Folgen sind doppelexponentiell, allerdings mit unterschiedlichen Exponenten – mit dem Ergebnis, dass die dünnsten Bäume mit wachsender Baumhöhe anteilig rasch (doppelexponentiell) selten werden.

Daraus folgt, dass die Knotenanzahlen für linken und rechten Teilbaum sehr unterschiedlich sein können. Z. B. kann ein AVL-Baum der Höhe 32–4=28 im Extremfall links einen Ast mit $2^{27}–1$ = 134217727 (vollständiger Binärbaum der Höhe 27) und rechts einen mit $n_{26}=514227$ (Fibonacci-Baum der Höhe 26) Knoten haben, was ein Knotenverhältnis von 134217727/514227 ≈ 261 ergibt. Bei einer Höhe von 64–5=59 kommen wir mit $2^{58}–1$ = 288230376151711743 und $n_{57}$ = 1548008755918 auf ein Verhältnis von ungefähr 186194.

## Suchtiefe

Die Suchtiefe eines Knotens ist die Anzahl der Kanten von der Wurzel bis zum Knoten. Bei einem externen Knoten in einem binären Suchbaum entspricht sie der Anzahl der erforderlichen Vergleiche; bei internen Knoten ist letztere um 1 höher.

### Maximale und minimale Suchtiefe eines externen Knotens

Die maximale Suchtiefe eines externen Knotens in einem Fibonacci-Baum ist $h$ mit $h$ als der Höhe.

Die minimale Suchtiefe eines externen Knotens in einem Fibonacci-Baum ist $\lceil {\tfrac {h}{2}}\rceil$. Beweis: Die beiden externen Blätter eines Baums der Höhe 1 haben Suchtiefe 1. Das rechte externe Blatt eines Fibonacci-Baums der Höhe 2 hat Suchtiefe 1. Bei der rekursiven Zusammensetzung eines Fibonacci-Baum der Höhe $h$ aus einem der Höhe $h-1$ und einem der Höhe $h-2$ findet sich die minimale Suchtiefe im Unterbaum der Höhe $h-2$. Daraus folgt die Behauptung. ■

Da das Verhältnis zwischen maximaler und minimaler Suchtiefe bei Rot-Schwarz-Bäumen $<2$ ist, können die Fibonacci-Bäume mit den Farben rot und schwarz nach den Regeln des Rot-Schwarz-Baums eingefärbt werden.

### Pfadlängensumme und mittlere Suchtiefe

Die Summe $s_{h}:=\sum _{x\in F_{h}}a(x)$ der Suchtiefen $a(x)$ über alle internen Knoten $x$ des Fibonacci-Baums $F_{h}$ der Stufe $h$, $S_{\mathfrak {e}}^{F_{h}}$ in der Notation des Abschnitts Suchtiefen und Pfadlängensummen, lässt sich wie folgt rekursiv berechnen:

    $s_{0}$$=$$0$ (leerer Suchbaum) $s_{1}$$=$$1$ (nur Wurzel) $s_{h}$$=$$1$$+$$s_{h-1}+n_{h-1}$$+$$s_{h-2}+n_{h-2}$ (neue Wurzel)(linkes Kind)(rechtes Kind) $=$$n_{h}+s_{h-1}+s_{h-2}$ $=$$f_{h+2}-1+s_{h-1}+s_{h-2}$für h ≥ 2.

Dies wird befriedigt durch

    ${\begin{aligned}s_{h}&=\left[h\left(3f_{h+2}+f_{h+1}\right)-2f_{h+2}-3f_{h+1}+5\right]/5\\&=\left[\left(4h-5\right)f_{h+1}+\left(3h-2\right)f_{h}+5\right]/5\end{aligned}}$.

Beweis:

    $f_{h+2}-1+s_{h-1}+s_{h-2}$
    $\quad =f_{h+2}-1+\left[(h-1)\left(3f_{h+1}+f_{h}\right)-2f_{h+1}-3f_{h}+5+(h-2)\left(3f_{h}+f_{h-1}\right)-2f_{h}-3f_{h-1}+5\right]/5$
    $\quad =\left[5f_{h+2}+h\left(3f_{h+1}+f_{h}\right)-3f_{h+1}-f_{h}-2f_{h+1}-5f_{h}+h\left(3f_{h}+f_{h-1}\right)-6f_{h}-2f_{h-1}-3f_{h-1}+5\right]/5$
    $\quad =\left[h\left(3f_{h+1}+4f_{h}+f_{h-1}\right)+5f_{h+2}-5f_{h+1}-12f_{h}-5f_{h-1}+5\right]/5$
    $\quad =\left[h\left(3f_{h+1}+4f_{h}+f_{h+1}-f_{h}\right)+5f_{h+2}-5f_{h+1}-12f_{h}-5f_{h+1}+5f_{h}+5\right]/5$
    $\quad =\left[h\left(4f_{h+1}+3f_{h}\right)+5f_{h+2}-10f_{h+1}-7f_{h}+5\right]/5$
    $\quad =\left[h\left(4f_{h+1}+3f_{h+2}-3f_{h+1}\right)+5f_{h+2}-10f_{h+1}-7f_{h+2}+7f_{h+1}+5\right]/5$
    $\quad =\left[h\left(3f_{h+2}+f_{h+1}\right)-2f_{h+2}-3f_{h+1}+5\right]/5$. ■

Die externe Pfadlänge, d. i. die Summe $\textstyle S_{\mathfrak {f}}^{F_{h}}:=\sum _{x\in F_{h}}b(x)$ der Suchtiefen $b(x)$ über alle externen Knoten $x=(x_{j},x_{j+1})$ mit $0\leqq j\leqq n$ des Fibonacci-Baums $F_{h}$ der Stufe $h$, ist dann

    ${\begin{aligned}S_{\mathfrak {f}}^{F_{h}}&=s_{h}+n_{h}\\&=\left[h\left(3f_{h+2}+f_{h+1}\right)-2f_{h+2}-3f_{h+1}+5\right]/5+f_{h+2}-1\\&=\left[4hf_{h+1}+\left(3h+3\right)f_{h}\right]/5.\end{aligned}}$

Damit ist $S_{\mathfrak {f}}^{F_{h}}$ die Folge A067331 in OEIS.

Vermöge der Formel von Moivre-Binet lässt sich hieraus für Fibonacci-Bäume über die mittlere Suchtiefe $s_{h}/n_{h}\;=\;S_{\mathfrak {e}}^{F_{h}}/n_{h}$ der Limes der Effizienz $v_{\mathfrak {e}}:=S_{\mathfrak {e}}^{F_{h}}/n_{h}/\log _{2}{n_{h}}$, vorhandene Schlüssel aufzusuchen, für $h\to \infty$ ableiten zu:

    ${\begin{aligned}v_{\mathfrak {e}}&\to h(3\Phi ^{h+2}+\Phi ^{h+1})/5/\Phi ^{h+2}/\log _{2}{n_{h}}\\&\to h(3+\Phi ^{-1})/5/\log _{2}{f_{h+2}}\\&\to h(3+\Phi -1)/5/(h+2)/\log _{2}{\Phi }\\&\to (2+\Phi )/5/\log _{2}{\Phi }\\&=(5/2+{\sqrt {5}}/2)/5/\log _{2}{\Phi }\\&=\Phi /{\sqrt {5}}/\log _{2}{\Phi }\\&\approx 1{,}042298.\end{aligned}}$

Für den Limes der Effizienz $v_{\mathfrak {f}}:=S_{\mathfrak {f}}^{F_{h}}/(n_{h}+1)/\log _{2}(n_{h}+1)$, das Nichtvorhandensein von Schlüsseln festzustellen, ergibt sich derselbe Wert.

## Anteil der unausgewogenen Knoten bei AVL-Bäumen

Eine etwas differenziertere Rekursion gestattet Einblick in die inneren Asymmetrien der AVL-Bäume. Sei dazu $U_{h,u,g}$ die Anzahl der AVL-Bäume der Höhe h mit u unausgewogenen (rechts- oder linkslastigen) und g ausgewogenen Knoten (mit gleich hohen Kindern). Dann ist nach Überlegungen analog zu oben

    $U_{0,0,0}=1$leerer Baum hat h=0, u=0, g=0 $U_{1,0,1}=1$nur Wurzel hat h=1, u=0, g=1 $U_{h,u,g}=\sum _{\upsilon ,\gamma }(U_{h-2,\upsilon ,\gamma }\cdot U_{h-1,u-1-\upsilon ,g-\gamma }\cdot 2+U_{h-1,\upsilon ,\gamma }\cdot U_{h-1,u-\upsilon ,g-1-\gamma })$,

denn bei den ungleich hohen Kindern kommt ein u-Knoten hinzu und bei den gleich hohen Kindern ein g-Knoten. Der Anteil der unausgewogenen Knoten an allen Knoten ist $u/(u+g)$, und dieser hat die Vielfachheit $U_{h,u,g}$, so dass sich als Anteil gemittelt über alle AVL-Bäume der Höhe h

    $u_{h}:=\left(\sum _{u,g}U_{h,u,g}\cdot u/(u+g)\right)/A_{h}$

ergibt. Denn die Anzahl aller AVL-Bäume der Höhe $h$ ist $\textstyle A_{h}:=\sum _{u,g}U_{h,u,g}$ mit demselben $A_{h}$ wie oben.

In Tabelle 2 finden sich Zahlenwerte für kleine $h$.

## Mittlere Suchtiefe bei AVL-Bäumen

### Abschätzung mittels Rekursion über die Höhe

Nach demselben Schema lassen sich mittlere Suchtiefen berechnen. Wir wählen der Vergleichbarkeit halber die Suchtiefe der externen Knoten (Blätter), d. i. die externe Pfadlänge. Sei dazu $P_{h,n,p}$ die Anzahl der AVL-Bäume der Höhe $h$ mit $n$ externen Blättern und der externen Pfadlänge $p$. Dann ist

    $P_{0,1,0}=1$ der leere Baum der Höhe 0 mit 1 externen Blatt und externer Pfadlänge 0  $P_{1,2,2}=1$der Baum der Höhe 1 (nur Wurzel) mit 2 externen Blättern und externer Pfadlänge 2 $P_{h,n,p}=\sum _{\nu ,\pi }(P_{h-2,\nu ,\pi }\cdot P_{h-1,n-\nu ,p-n-\pi }\cdot 2+P_{h-1,\nu ,\pi }\cdot P_{h-1,n-\nu ,p-n-\pi })$,

denn bei der rekursiven Zusammensetzung zweier AVL-Bäume erhöht sich die Zahl der externen Blätter von

    $n_lundn_raufn_l+n_r=:$ n

und die externe Pfadlänge von

    $p_lundp_raufp_l+p_r+n=:$ p,

da sich der Weg zur Wurzel für jedes Blatt um 1 verlängert. Die Anzahl aller AVL-Bäume der Höhe $h$ ist

    $A_{h}:=\sum _{n,p}P_{h,n,p}$.

Es ist dasselbe $A_{h}$ wie oben.

| Höhe | Anzahl Bäume | Anteil unausge- wogene | Anteil unausge- wogene | Anzahl externe Blätter | Anzahl externe Blätter | Anzahl externe Blätter | externe Pfadlänge | externe Pfadlänge | externe Pfadlänge | mittl. Verlän- gerung |
| - | - | - | - | - | - | - | - | - | - | - |
| $h$ | $A_{h}$ | Knoten | Wurzeln | ${\underline {n}}_{h}$ | $n_h$ | ${\overline {n}}_{h}$ | ${\underline {p}}_{h}$ | $p_h$ | ${\overline {p}}_{h}$ | $v_h$ |
| 1 | 1 | 0,000 | 0,00000 | 2 | 2,0000 | 2 | 2 | 2,0000 | 2 | 1,0000 |
| 2 | 3 | 0,333 | 0,66667 | 3 | 3,3333 | 4 | 5 | 6,0000 | 8 | 1,0344 |
| 3 | 15 | 0,311 | 0,40000 | 5 | 6,1333 | 8 | 12 | 16,533 | 24 | 1,0263 |
| 4 | 315 | 0,303 | 0,28571 | 8 | 11,467 | 16 | 25 | 41,524 | 64 | 1,0260 |
| 5 | 108675 | 0,285 | 0,08696 | 13 | 22,470 | 32 | 50 | 103,34 | 160 | 1,0228 |
| 6 | 11878720875 | 0,274 | 5,76e-3 | 21 | 44,876 | 64 | 96 | 251,21 | 384 | 1,0194 |
| 7 | 141106591 466142946875 | 0,269 | 1,83e-5 | 34 | 89,751 | 128 | 180 | 592,16 | 896 | 1,0167 |
| 8 | 19911 070158545297 149037891328 865229296875 | 0,267 | 1,7e-10 | 55 | 179,50 | 256 | 331 | 1363,8 | 2048 | 1,0146 |
| Tabelle 2: Unausgewogene Knoten und externe Pfadlänge nach Höhe |||||||||||

Die Spalte Anteil unausgewogene Knoten enthält das $u_{h}$ des Abschnitts #Anteil der unausgewogenen Knoten bei AVL-Bäumen, wogegen die Spalte Anteil unausgewogene Wurzeln den Anteil der Bäume mit unausgewogener Wurzel innerhalb der Gesamtheit der AVL-Bäume der Höhe $h$ bedeutet.

In der Spalte $v_h$ ist die externe Pfadlänge mit der idealen (minimalen) externen Pfadlänge ${\underline {p}}_{n}$, die von der Knotenzahl $n$ abhängt (s. Tabelle 3), verglichen und dann über alle AVL-Bäume der Höhe $h$ gemittelt.

### Genaue Rechnung

Die Annahme von gleichen Wahrscheinlichkeiten für alle AVL-Baumformen ist eine Vereinfachung. Zwar kann eine jede mögliche Form eines Binärbaums durch gezielte Einfügungen aufgebaut werden, bei den AVL-Bäumen gibt es aber bevorzugte Formen, die nach Rotationen häufiger entstehen als andere. Werden alle Reihenfolgen (Permutationen) der Einfügung als gleich wahrscheinlich angesehen, dann ergibt sich z. B. bei den 17 AVL-Bäumen mit der Knotenzahl 7 (s. Tabelle 3) beim ausgewogenen Baum (einem vollständigen Binärbaum der Höhe 3) eine Häufigkeit von 2160 und bei den restlichen 16 (die allesamt Fibonacci-Bäume der Höhe 4 sind) für die eine Hälfte eine Häufigkeit von 144 und für die andere eine von 216.

| Kno- ten- zahl | mittl. Höhe | Anzahl Bäume | Anteil unausge- wogener | Anteil unausge- wogener | Häufigkeit | Häufigkeit | externe Pfad- länge | externe Pfad- länge | externe Pfad- länge | mittl. Verlän- gerung |
| - | - | - | - | - | - | - | - | - | - | - |
| $n$ | $h_n$ | $A_{n}$ | Knoten | Wurzeln | ${\underline {f}}_{n}$ | ${\overline {f}}_{n}$ | ${\underline {p}}_{n}$ | $p_n$ | ${\overline {p}}_{n}$ | $v_n$ |
| 1 | 1,00 | 1 | 0,000 | 0,000 | 1 | 1 | 2 | 2,00 | 2 | 1,0000 |
| 2 | 2,00 | 2 | 0,500 | 1,000 | 1 | 1 | 5 | 5,00 | 5 | 1,0000 |
| 3 | 2,00 | 1 | 0,000 | 0,000 | 6 | 6 | 8 | 8,00 | 8 | 1,0000 |
| 4 | 3,00 | 4 | 0,500 | 1,000 | 6 | 6 | 12 | 12,00 | 12 | 1,0000 |
| 5 | 3,00 | 6 | 0,280 | 0,600 | 12 | 36 | 16 | 16,00 | 16 | 1,0000 |
| 6 | 3,00 | 4 | 0,167 | 0,000 | 144 | 216 | 20 | 20,00 | 20 | 1,0000 |
| 7 | 3,57 | 17 | 0,327 | 0,571 | 144 | 2160 | 24 | 24,57 | 25 | 1,0238 |
| 8 | 4,00 | 32 | 0,393 | 1,000 | 288 | 3240 | 29 | 29,36 | 30 | 1,0123 |
| 9 | 4,00 | 44 | 0,333 | 0,714 | 3456 | 25920 | 34 | 34,24 | 35 | 1,0070 |
| 10 | 4,00 | 60 | 0,286 | 0,429 | 25056 | 194400 | 39 | 39,07 | 40 | 1,0018 |
| 11 | 4,00 | 70 | 0,249 | 0,117 | 114048 | 2332800 | 44 | 44,00 | 44 | 1,0000 |
| 12 | 4,19 | 184 | 0,267 | 0,193 | 466560 | 17418240 | 49 | 49,19 | 50 | 1,0039 |
| 13 | 4,51 | 476 | 0,311 | 0,509 | 933120 | 242611200 | 54 | 54,58 | 56 | 1,0108 |
| 14 | 4,79 | 872 | 0,342 | 0,790 | 8823168 | 2774865600 | 59 | 60,10 | 62 | 1,0187 |
| 15 | 4,96 | 1553 | 0,351 | 0,888 | 116173440 | 54979430400 | 64 | 65,72 | 68 | 1,0268 |
| 16 | 5,00 | 2720 | 0,340 | 0,776 | 519747840 | 149860238400 | 70 | 71,41 | 73 | 1,0201 |
| 17 | 5,00 | 4288 | 0,324 | 0,609 | 2769500160 | 1978587648000 | 76 | 77,13 | 79 | 1,0149 |
| 18 | 5,00 | 6312 | 0,309 | 0,453 | 60134731776 | 22812754464000 | 82 | 82,88 | 85 | 1,0107 |
| 19 | 5,00 | 9004 | 0,296 | 0,295 | 904805406720 | 398794586112000 | 88 | 88,66 | 91 | 1,0075 |
| 20 | 5,02 | 16088 | 0,287 | 0,179 | 5394695644800 | 3968960489625600 | 94 | 94,52 | 97 | 1,0056 |
| 21 | 5,10 | 36900 | 0,287 | 0,159 | 10789391289600 | 74716118765568000 | 100 | 100,49 | 103 | 1,0049 |
| 22 | 5,22 | 82984 | 0,293 | 0,237 | 97480461657600 | 1134885141276480000 | 106 | 106,55 | 110 | 1,0052 |
| 23 | 5,38 | 174374 | 0,304 | 0,380 | 1362760719022080 | 28970685819518976000 | 112 | 112,71 | 117 | 1,0064 |
| 24 | 5,54 | 346048 | 0,315 | 0,543 | 7172727971696640 | 337716405039775104000 | 118 | 118,95 | 123 | 1,0080 |
| 25 | 5,70 | 653096 | 0,325 | 0,691 | 70893673900600320 | 7478785384139059200000 | 124 | 125,26 | 130 | 1,0101 |
| 26 | 5,82 | 1199384 | 0,331 | 0,795 | 990569400644966400 | 134732114837823140352000 | 130 | 131,63 | 137 | 1,0125 |
| Tabelle 3: Unausgewogene Knoten und externe Pfadlänge nach Einfügereihenfolge |||||||||||

Bei der Aufstellung der Tabelle 3 wurden pro Knotenzahl $n$ alle Reihenfolgen der Einfügung nach dem AVL-Einfügealgorithmus mit demselben Gewicht versehen. (Deshalb summieren die Häufigkeiten $f_{n}$ zu n! auf.) Der große Unterschied zwischen minimaler und maximaler Häufigkeit ${\underline {f}}_{n}$ resp. ${\overline {f}}_{n}$ zeigt, dass die entstehenden Baumformen sehr unterschiedlich häufig sind, wobei die häufigsten gleichzeitig minimale externe Pfadlänge ${\underline {p}}_{n}$ haben. Letzteres ${\underline {p}}_{n}$ ist gleichzeitig Bezugspunkt für die mittlere Verlängerung der externen Pfadlänge $v_n.$ Fibonacci-Bäume sind durchaus selten, haben aber nicht notwendigerweise maximale externe Pfadlänge ${\overline {p}}_{n}$.

Diese Häufigkeiten sind wesentlich schwerer zu berechnen als die obigen Baumanzahlen $P_{h,n,p}$ und Verlängerungen der Pfadlänge $v_h,$ bei denen die AVL-Bäume einer festen Höhe $h$ als gleich wahrscheinlich angenommen werden. Für kleine Bäume unterscheiden sich $v_n$ und $v_h$ allerdings nur geringfügig. R. W. Floyd schätzt den mittleren Aufwand, unter $n$ Schlüsseln das Fehlen eines $(n\!+\!1\!)$-ten festzustellen, auf $1{,}01\log _{2}{n}+0{,}01$, was asymptotisch einem Wert von $1{,}01$ für $v_n$ entspricht.

Die Spalten $A_{n}$, ${\underline {p}}_{n}$ und ${\overline {p}}_{n}$ sind die Folgen A006265, A001855 resp. A228155 in OEIS.

## Flankentiefe

Als linke bzw. rechte Flankentiefe sei die Länge des Pfades von der Wurzel bis zum Minimum resp. zum Maximum bezeichnet. Da man durch links-rechts-Spiegelung eines AVL-Baums wieder einen AVL-Baum derselben Höhe erhält, haben linke wie rechte Flankentiefe dieselbe Wertemenge. Für einen AVL-Baum der Höhe $h$ ist sie höchstens ${\overline {d}}_{h}=h-1$ und mindestens

    ${\underline {d}}_{h}=\lceil {\tfrac {h}{2}}\rceil -1$,

entsprechend den Überlegungen zur minimalen Suchtiefe von Fibonacci-Bäumen.

Auf ähnliche Weise wie oben lässt sich die linke und rechte Flankentiefe mitteln über alle AVL-Bäume der Höhe $h$. Sei dazu $d_{h,l,r}$ die Anzahl der AVL-Bäume der Höhe $h$ mit linker Flankentiefe $l$ und rechter Flankentiefe $r$. Dann ist

    $d_{1,0,0}=1$
    $d_{2,1,0}=d_{2,0,1}=d_{2,1,1}=1$
    $d_{h,l,r}=\sum _{\lambda ,\rho }(d_{h-1,l-1,\rho }\cdot d_{h-2,\lambda ,r-1}\,+\,d_{h-2,l-1,\rho }\cdot d_{h-1,\lambda ,r-1}\,+\,d_{h-1,l-1,\rho }\cdot d_{h-1,\lambda ,r-1})$

denn bei der rekursiven Zusammensetzung zweier AVL-Bäume erhöht sich die Flankentiefe auf beiden Seiten um 1 und es können in jeder der Gruppen „links höher“, „rechts höher“ und „gleich hoch“ alle Möglichkeiten links mit allen Möglichkeiten rechts kombiniert und diese Anzahlen insgesamt aufsummiert werden. Als Kontrolle gilt: Die Anzahl aller AVL-Bäume der Höhe $h$ ist

    $A_{h}:=\sum _{l,r}d_{h,l,r}$.

Es ist dasselbe $A_{h}$ wie oben.

Die mittlere linke wie rechte Flankentiefe für einen AVL-Baum der Höhe $h$ ist dann

    $d_h$ $:=\left(\sum _{l,r}l\cdot d_{h,l,r}\right)/A_{h}$.

Zahlenwerte für kleine $h$ sind in Tabelle 1.

## Mittlere Abstiegstiefe beim Löschen

Ähnlich lässt sich eine mittlere Abstiegstiefe berechnen, die beim Löschen eines Knotens von seiner Höhe bis zu den (Halb-)Blättern zu seiner Linken oder Rechten hinabgestiegen werden muss, um einen Knoten zu finden, der an die Stelle des zu löschenden Knotens treten kann. Für einen einzelnen Knoten auf der Höhe $h$ entspricht ihr Mittelwert dem soeben berechneten $d_h.$

Der Mittelwert über alle Knoten eines AVL-Baumes ist aber wesentlich niedriger, da die meisten Knoten auf geringer Höhe liegen. Sei dazu $D_{h,n,L,l,R,r}$ die Anzahl der AVL-Bäume der Höhe $h$ mit $n$ Knoten, linker Flankentiefe $l$ und Flankentiefensumme $L$ und rechter Flankentiefe $r$ und Flankentiefensumme $R$. Dabei sei Flankentiefensumme die Summe aller linken resp. rechten Flankentiefen eines gegebenen Baums. Dann ist

    $D_{1,1,0,0,0,0}=1$$\cdot$AVL-Baum mit 1 Knoten $D_{2,2,1,1,0,0}=1$$/$AVL-Baum mit 2 Knoten linkslastig $D_{2,2,0,0,1,1}=1$$\backslash$AVL-Baum mit 2 Knoten rechtslastig $D_{2,3,1,1,1,1}=1$$\wedge$AVL-Baum mit 3 Knoten
    $D_{h,n,L,l,R,r}=\sum _{\lambda ,\rho ,\;\;n=n_{l}+1+n_{r}, \atop L=L_{l}+l+L_{r},\;R=R_{l}+r+R_{r}}$ $(\,D_{h-1,n_{l},L_{l},l-1,R_{l},\rho }\cdot D_{h-2,n_{r},L_{r},\lambda ,R_{r},r-1}$  $+D_{h-2,n_{l},L_{l},l-1,R_{l},\rho }\cdot D_{h-1,n_{r},L_{r},\lambda ,R_{r},r-1}$  $+D_{h-1,n_{l},L_{l},l-1,R_{l},\rho }\cdot D_{h-1,n_{r},L_{r},\lambda ,R_{r},r-1\,}\,)$

denn bei der rekursiven Zusammensetzung zweier AVL-Bäume erhöhen sich durch das Hinzukommen der neuen Wurzel die Flankentiefen auf beiden Seiten um 1, bei der linken und rechten Flankentiefensumme kommt zum Beitrag der 2 Bäume noch die beziehentliche Flankentiefe hinzu und es können in jeder der Gruppen „links höher“, „rechts höher“ und „gleich hoch“ alle Möglichkeiten links mit allen Möglichkeiten rechts kombiniert und diese Anzahlen insgesamt aufsummiert werden.

Die Anzahl der AVL-Bäume der Höhe $h$ mit $n$ Knoten und linker Flankentiefensumme $L$ ist

    $B_{h,n,L}:=\sum _{R,l,r}D_{h,n,L,l,R,r}$.

Diese Bäume haben damit pro Knoten die mittlere linke Flankentiefe ${\frac {L}{n}}$. Die Flankentiefe gemittelt über alle AVL-Bäume der Höhe $h$ ist somit

    $\Delta _{h}:=\left(\sum _{n,L}B_{h,n,L}\cdot L/n\right)/A_{h}$.

Denn wir haben $\textstyle A_{h}=\sum _{n,L}B_{h,n,L}$ mit demselben $A_{h}$ wie oben.

Da aus Symmetriegründen die Länge eines Weges von der Wurzel zu einem Knoten auf einer bestimmten Höhe bei Einheits-Zugriffswahrscheinlichkeiten nicht von Richtungswechseln abhängt, ist die mittlere Abstiegstiefe gemittelt über alle AVL-Bäume der Höhe $h$ ebenfalls $\Delta _{h}$.

Einige Zahlenwerte:

| $h$ | ${\underline {d}}_{h}$ | $d_h$ | ${\overline {d}}_{h}$ | $\Delta _{h}$ |
| - | - | - | - | - |
| 1 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0,6667 | 1 | 0,27778 |
| 3 | 1 | 1,5333 | 2 | 0,49921 |
| 4 | 1 | 2,4095 | 3 | 0,66886 |
| 5 | 2 | 3,3714 | 4 | 0,79391 |
| 6 | 2 | 4,3687 | 5 | 0,87686 |
| 7 | 3 | 5,3686 | 6 | 0,92801 |
| 8 | 3 | 6,3686 | 7 | 0,95865 |
| 9 | 4 | 7,3686 | 8 | 0,97660 |
| 10 | 4 | 8,3686 | 9 | 0,98693 |
| Tabelle 1 |||||

Die ganz einfache Überlegung aus dem Abschnitt Löschen liefert

    $\lim _{h\to \infty }\Delta _{h}=1$.
