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 des goldenen Schnittes. Ideal wäre für einen Binärbaum natürlich die Basis , 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. mini|240px|Fibonacci-Baum der Stufe 6 mit Balance-Faktoren (grün) und Höhenangaben (rot)
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 der Stufe 0 ist der leere Baum. Der Fibonacci-Baum der Stufe 1 ist ein Baum, der nur aus einem Knoten besteht. Ein Fibonacci-Baum der Stufe (mit ) besteht aus einer Wurzel, deren linkes Kind ein Fibonacci-Baum der Stufe und deren rechtes Kind ein Fibonacci-Baum der Stufe ist.
Eigenschaften Alle internen Knoten (Knoten, die nicht Blätter sind) haben den Balance-Faktor −1. Der Fibonacci-Baum der Stufe (mit ) hat die Höhe .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.
Ist die Anzahl der Knoten des Fibonacci-Baums der Stufe , dann gilt
für
Ist die Anzahl der Blattknoten des Fibonacci-Baums der Stufe , dann gilt
für
Ist die Anzahl der Einfügepunkte (Halbblätter; 1 Blatt = 2 Halbblätter) des Fibonacci-Baums der Stufe , dann gilt
für
Mit Hilfe der Bezeichnung für die -te Fibonacci-Zahl lassen sich diese Größen auch so ausdrücken:
(Für jeden gerichteten Binärbaum gilt .)
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
| || || || || für und |- | || || || || für .
Damit lässt sich die Höhe in Abhängigkeit von der Knotenanzahl abschätzen zu
| || laut Knuth Theorem A die Formulierung von Adelson-Velsky / Landis |} mit , und .
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 dünnster AVL-Bäume der Höhe {| class="left" style="text-align: left;" |- | a0 = ||1 |- | a1 = ||1 |- |style="width:2.5em" | ah = |style="width:11em" | (ah–1 • ah–2) |style="width:7em" | • 2 |style="width:11em" | | (für h ≥ 2)
| (h–1 links & h–2 rechts) | + umgekehrt
Das ist in geschlossener Form , welches sich für der Funktion
mit annähert.
Die Anzahl aller AVL-Bäume der Höhe lässt sich wie folgt berechnen:#Knuth a. a. O., S. 467.
{| class="left" style="text-align: left;" |- | A0 = ||1 |- | A1 = ||1 |- |style="width:2.5em" | Ah = |style="width:11em" | (Ah–1 • Ah–2) |style="width:7em" | • 2 |style="width:11em" | + (Ah–1 • Ah–1) | (für h ≥ 2)
| (h–1 links & h–2 rechts) | + umgekehrt | + (h–1 links & h–1 rechts)
Es handelt sich um die , die sich für der Funktion
mit oder 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 227–1 = 134217727 (vollständiger Binärbaum der Höhe 27) und rechts einen mit (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 258–1 = 288230376151711743 und n57 = 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 mit als der Höhe.
mini|220px|2 Fibonacci-Bäume der Schwarztiefe 3 Die minimale Suchtiefe eines externen Knotens in einem Fibonacci-Baum ist . 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 aus einem der Höhe und einem der Höhe findet sich die minimale Suchtiefe im Unterbaum der Höhe . Daraus folgt die Behauptung. ■
Da das Verhältnis zwischen maximaler und minimaler Suchtiefe bei Rot-Schwarz-Bäumen 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 der Suchtiefen über alle internen Knoten des Fibonacci-Baums der Stufe , in der Notation des Abschnitts Suchtiefen und Pfadlängensummen, lässt sich wie folgt rekursiv berechnen: {| class="left" style="text-align: left;" |- | ||style="text-align:center; width:1.5em" | || |- | || || (leerer Suchbaum) |- | ||style="text-align:center; width:1.5em" | || |- | || || (nur Wurzel) |- | ||style="text-align:center; width:1.5em" | || ||style="text-align:center; width:6em" | || ||style="text-align:center; width:6em" | || |- | || || (neue Wurzel) || || (linkes Kind) || || (rechtes Kind) |- | ||style="text-align:center; width:1.5em" | || colspan="5" | |- | ||style="text-align:center; width:1.5em" | || colspan="4" | || für h ≥ 2.
Dies wird befriedigt durch .
Beweis:
. ■
Die externe Pfadlängeexternal path length bei #Knuth a. a. O. pp. 399–400, d. i. die Summe der Suchtiefen über alle externen Knoten mit des Fibonacci-Baums der Stufe , ist dann
Damit ist die .
Vermöge der Formel von Moivre-Binet lässt sich hieraus für Fibonacci-Bäume über die mittlere Suchtiefe der Limes der Effizienz , vorhandene Schlüssel aufzusuchen, für ableiten zu:
Für den Limes der Effizienz , 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 Uh,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 {| class="left" style="text-align: left;" |- | || leerer Baum hat || style="width:28em;" | h=0, u=0, g=0 |- | || nur Wurzel hat || h=1, u=0, g=1 |- | colspan="3" | , |} 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 , und dieser hat die Vielfachheit , so dass sich als Anteil gemittelt über alle AVL-Bäume der Höhe h
ergibt. Denn die Anzahl aller AVL-Bäume der Höhe ist mit demselben wie oben.
In Tabelle 2 finden sich Zahlenwerte für kleine .
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 die Anzahl der AVL-Bäume der Höhe mit externen Blättern und der externen Pfadlänge . Dann ist {| class="table left" style="text-align: left;"
| || || der leere Baum der Höhe 0 mit 1 externen Blatt und externer Pfadlänge 0 ||
| || || der Baum der Höhe 1 (nur Wurzel) mit 2 externen Blättern und externer Pfadlänge 2 || |- | colspan="4" | , |} denn bei der rekursiven Zusammensetzung zweier AVL-Bäume erhöht sich die Zahl der externen Blätter von {| class="table left" style="text-align: center;"
| nl || style="width:2em" | und || nr || style="width:4em" | auf || style="text-align: left;width:4.0em" | nl+nr || =: n
und die externe Pfadlänge von {| class="table left" style="text-align: center;"
| pl || style="width:2em" | und || pr || style="width:4em" | auf || style="text-align: left;width:4.0em" | pl+pr+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 ist . Es ist dasselbe wie oben.
Höhe AnzahlBäume Anteilunausge-wogene AnzahlexterneBlätter externePfadlänge mittl.Verlän-gerung Knoten Wurzeln nh ph vh 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 141106591466142946875 0,269 1,83e-5 34 89,751 128 180 592,16 896 1,0167 8 19911070158545297149037891328865229296875 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 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 bedeutet.
In der Spalte vh ist die externe Pfadlänge mit der idealen (minimalen) externen Pfadlänge , die von der Knotenzahl abhängt (s. Tabelle 3), verglichen und dann über alle AVL-Bäume der Höhe 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.