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 $Φ := \frac{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$ .^[1]

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$
	$= \frac{1}{\sqrt{5}} [$	$(\frac{1 + \sqrt{5}}{2}) h + 2$	$- (\frac{1 - \sqrt{5}}{2}) h + 2]$	$- 1$
	$≧$	$\frac{Φ^{h + 2}}{\sqrt{5}}$	$- \frac{(- Φ^{- 1})^{4}}{\sqrt{5}}$	$- 1$ für $h \geq 1$ und
	$≧$	$\frac{Φ^{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$	$≦ c \log_{2} (n + d) + b$
	$≦ c \log_{2} (n + 2) + b$ ^[2]

mit

c := \frac{1}{\log_{2} Φ} \approx 1,440420

,

b := \frac{c}{2} \log_{2} 5 - 2 \approx - 0,327724

und

d := \frac{1}{Φ^{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₀ =	1
a₁ =	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^{Φ^{h + f} - 1}

mit $f := 1 - \frac{\log_{Φ} 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:^[3]

A₀ =	1
A₁ =	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_{𝖠 𝟢𝟤𝟫𝟩𝟧𝟪} \approx 1,436873$ oder $K := \log_{2} \log_{2} k \approx - 0,935305$ annähert.^[4]

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²⁷–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⁵⁸–1 = 288230376151711743 und n₅₇ = 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 $⌈ \frac{h}{2} ⌉$ .
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_{𝔢}^{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{matrix} s_{h} & = [h (3 f_{h + 2} + f_{h + 1}) - 2 f_{h + 2} - 3 f_{h + 1} + 5] / 5 \\ = [(4 h - 5) f_{h + 1} + (3 h - 2) f_{h} + 5] / 5 \end{matrix}

.

Beweis:

f_{h + 2} - 1 + s_{h - 1} + s_{h - 2}

= f_{h + 2} - 1 + [(h - 1) (3 f_{h + 1} + f_{h}) - 2 f_{h + 1} - 3 f_{h} + 5 + (h - 2) (3 f_{h} + f_{h - 1}) - 2 f_{h} - 3 f_{h - 1} + 5] / 5

= [5 f_{h + 2} + h (3 f_{h + 1} + f_{h}) - 3 f_{h + 1} - f_{h} - 2 f_{h + 1} - 5 f_{h} + h (3 f_{h} + f_{h - 1}) - 6 f_{h} - 2 f_{h - 1} - 3 f_{h - 1} + 5] / 5

= [h (3 f_{h + 1} + 4 f_{h} + f_{h - 1}) + 5 f_{h + 2} - 5 f_{h + 1} - 12 f_{h} - 5 f_{h - 1} + 5] / 5

= [h (3 f_{h + 1} + 4 f_{h} + f_{h + 1} - f_{h}) + 5 f_{h + 2} - 5 f_{h + 1} - 12 f_{h} - 5 f_{h + 1} + 5 f_{h} + 5] / 5

= [h (4 f_{h + 1} + 3 f_{h}) + 5 f_{h + 2} - 10 f_{h + 1} - 7 f_{h} + 5] / 5

= [h (4 f_{h + 1} + 3 f_{h + 2} - 3 f_{h + 1}) + 5 f_{h + 2} - 10 f_{h + 1} - 7 f_{h + 2} + 7 f_{h + 1} + 5] / 5

= [h (3 f_{h + 2} + f_{h + 1}) - 2 f_{h + 2} - 3 f_{h + 1} + 5] / 5

. ■

Die externe Pfadlänge^[5], d. i. die Summe $S_{𝔣}^{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 ≦ j ≦ n$ des Fibonacci-Baums $F_{h}$ der Stufe $h$ , ist dann

\begin{matrix} S_{𝔣}^{F_{h}} & = s_{h} + n_{h} \\ = [h (3 f_{h + 2} + f_{h + 1}) - 2 f_{h + 2} - 3 f_{h + 1} + 5] / 5 + f_{h + 2} - 1 \\ = [4 h f_{h + 1} + (3 h + 3) f_{h}] / 5. \end{matrix}

Damit ist $S_{𝔣}^{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_{𝔢}^{F_{h}} / n_{h}$ der Limes der Effizienz $v_{𝔢} := S_{𝔢}^{F_{h}} / n_{h} / \log_{2} n_{h}$ , vorhandene Schlüssel aufzusuchen, für $h \to \infty$ ableiten zu:

\begin{matrix} v_{𝔢} & \to h (3 Φ^{h + 2} + Φ^{h + 1}) / 5 / Φ^{h + 2} / \log_{2} n_{h} \\ \to h (3 + Φ^{- 1}) / 5 / \log_{2} f_{h + 2} \\ \to h (3 + Φ - 1) / 5 / (h + 2) / \log_{2} Φ \\ \to (2 + Φ) / 5 / \log_{2} Φ \\ = (5 / 2 + \sqrt{5} / 2) / 5 / \log_{2} Φ \\ = Φ / \sqrt{5} / \log_{2} Φ \\ \approx 1,042298. \end{matrix}

Für den Limes der Effizienz $v_{𝔣} := S_{𝔣}^{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_{υ, γ} (U_{h - 2, υ, γ} \cdot U_{h - 1, u - 1 - υ, g - γ} \cdot 2 + U_{h - 1, υ, γ} \cdot U_{h - 1, u - υ, g - 1 - γ})$ ,

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} := (\sum_{u, g} U_{h, u, g} \cdot u / (u + g)) / A_{h}

ergibt. Denn die Anzahl aller AVL-Bäume der Höhe $h$ ist $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_{ν, π} (P_{h - 2, ν, π} \cdot P_{h - 1, n - ν, p - n - π} \cdot 2 + P_{h - 1, ν, π} \cdot P_{h - 1, n - ν, p - n - π})$ ,

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

n_l

und

n_r

auf

n_l+n_r

=: n

und die externe Pfadlänge von

p_l

und

p_r

auf

p_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		Anzahl externe Blätter			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		Häufigkeit		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}$ .^[6]

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.^[7] R. W. Floyd^[8] 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,^[9] A001855^[10] resp. A228155^[11] 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} = ⌈ \frac{h}{2} ⌉ - 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_{λ, ρ} (d_{h - 1, l - 1, ρ} \cdot d_{h - 2, λ, r - 1} + d_{h - 2, l - 1, ρ} \cdot d_{h - 1, λ, r - 1} + d_{h - 1, l - 1, ρ} \cdot d_{h - 1, λ, 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

:= (\sum_{l, r} l \cdot d_{h, l, r}) / 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$	$∖$	AVL-Baum mit 2 Knoten rechtslastig
$D_{2, 3, 1, 1, 1, 1} = 1$	$\land$	AVL-Baum mit 3 Knoten

$D_{h, n, L, l, R, r} = \sum_{\binom{λ, ρ, n = n_{l} + 1 + n_{r},}{L = L_{l} + l + L_{r}, R = R_{l} + r + R_{r}}}$	$(D_{h - 1, n_{l}, L_{l}, l - 1, R_{l}, ρ} \cdot D_{h - 2, n_{r}, L_{r}, λ, R_{r}, r - 1}$
	$+ D_{h - 2, n_{l}, L_{l}, l - 1, R_{l}, ρ} \cdot D_{h - 1, n_{r}, L_{r}, λ, R_{r}, r - 1}$
	$+ D_{h - 1, n_{l}, L_{l}, l - 1, R_{l}, ρ} \cdot D_{h - 1, n_{r}, L_{r}, λ, 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

Δ_{h} := (\sum_{n, L} B_{h, n, L} \cdot L / n) / A_{h}

.

Denn wir haben $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 $Δ_{h}$ .

Einige Zahlenwerte:

$h$	${\underline{d}}_{h}$	d_h	${\overline{d}}_{h}$	$Δ_{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} Δ_{h} = 1

.

Siehe auch

Literatur

Donald E. Knuth: The Art of Computer Programming. 2. Auflage. Volume 3: Sorting and Searching. Addison-Wesley, Reading MA 1997, ISBN 0-201-89685-0, 6.2.3 Balanced Trees (englisch).

Kurt Mehlhorn Datenstrukturen und effiziente Algorithmen Teubner Stuttgart 1988, ISBN 3-519-12255-3.

Einzelnachweise

↑ Die Höhe als Maximalzahl der Knotenebenen oder zahlenmäßig gleich, wenn es wie bei #Knuth (schlüssellose) externe Blätter gibt, als Maximalzahl der Kanten vom externen Blatt zur Wurzel.
↑ laut Knuth Theorem A die Formulierung von Adelson-Velsky / Landis
↑ #Knuth a. a. O., S. 467.
↑ A. V. Aho and N. J. A. Sloane: Some Doubly Exponential Sequences. In: Fib. Quart., 11, Bell Laboratories Murray Hill, New Jersey. 1970, S. 429–437 (englisch, math.ca [PDF]).
↑ external path length bei #Knuth a. a. O. pp. 399–400
↑ Bspw. hat der Fibonacci-Baum mit $n = 20$ die externe Pfadlänge $p = 96$ . Der AVL-Baum mit $n = 20$ und $p = 97$ hat auf der einen Seite den vollständigen Binärbaum mit 15 Knoten und auf der anderen Seite einen Fibonacci-Baum mit 4 Knoten.
↑ Bei den Anteilen der Bäume mit unausgewogener Wurzel wird allerdings die unterschiedliche Gewichtung in extremer Form sichtbar.
↑ zitiert nach #Knuth a. a. O., S. 468
↑ https://oeis.org/A006265
↑ https://oeis.org/A001855
↑ https://oeis.org/A228155

[1] Die Höhe als Maximalzahl der Knotenebenen oder zahlenmäßig gleich, wenn es wie bei #Knuth (schlüssellose) externe Blätter gibt, als Maximalzahl der Kanten vom externen Blatt zur Wurzel.

[2] ut Knuth Theorem A die Formulierung von Adelson-Velsky / Landis

[3] #Knuth a. a. O., S. 467.

[4] A. V. Aho and N. J. A. Sloane: Some Doubly Exponential Sequences. In: Fib. Quart., 11, Bell Laboratories Murray Hill, New Jersey. 1970, S. 429–437 (englisch, math.ca [PDF]).

[5] external path length bei #Knuth a. a. O. pp. 399–400

[6] Bspw. hat der Fibonacci-Baum mit $n = 20$ die externe Pfadlänge $p = 96$ . Der AVL-Baum mit $n = 20$ und $p = 97$ hat auf der einen Seite den vollständigen Binärbaum mit 15 Knoten und auf der anderen Seite einen Fibonacci-Baum mit 4 Knoten.

[7] Bei den Anteilen der Bäume mit unausgewogener Wurzel wird allerdings die unterschiedliche Gewichtung in extremer Form sichtbar.

[8] zitiert nach #Knuth a. a. O., S. 468

[9] ttps://oeis.org/A006265

[10] ttps://oeis.org/A001855

[11] ttps://oeis.org/A228155

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]