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.
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 Bearbeiten
Die rekursive Definition erfolgt in der Art:
Eigenschaften Bearbeiten
- Alle internen Knoten (Knoten, die nicht Blätter sind) haben den Balance-Faktor −1.
- Der Fibonacci-Baum der Stufe (mit ) hat die Höhe .
- Ist die Anzahl der Knoten des Fibonacci-Baums der Stufe , dann gilt
- Ist die Anzahl der Blattknoten des Fibonacci-Baums der Stufe , dann gilt
- Ist die Anzahl der Einfügepunkte (Halbblätter; 1 Blatt = 2 Halbblätter) des Fibonacci-Baums der Stufe , dann gilt
- Mit Hilfe der Bezeichnung für die -te Fibonacci-Zahl lassen sich diese Größen auch so ausdrücken:
- 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
- Damit lässt sich die Höhe in Abhängigkeit von der Knotenanzahl abschätzen zu
Andere dünnste AVL-Bäume Bearbeiten
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
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:
Es handelt sich um die Folge A029758 in OEIS, 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 Bearbeiten
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 Bearbeiten
Die maximale Suchtiefe eines externen Knotens in einem Fibonacci-Baum ist mit als der Höhe.
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 Bearbeiten
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:
Dies wird befriedigt durch
Beweis:
Die externe Pfadlänge, d. i. die Summe der Suchtiefen über alle externen Knoten mit des Fibonacci-Baums der Stufe , ist dann
Damit ist 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 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 Bearbeiten
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
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 Bearbeiten
Abschätzung mittels Rekursion über die Höhe Bearbeiten
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
denn bei der rekursiven Zusammensetzung zweier AVL-Bäume erhöht sich die Zahl der externen Blätter von
und die externe Pfadlänge von
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 | Anzahl Bäume | Anteil unausge- wogene | Anzahl externe Blätter | externe Pfadlänge | mittl. Verlän- gerung | |||||
| Knoten | Wurzeln | |||||||||
| 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 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 Bearbeiten
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 | ||||
| Knoten | Wurzeln | |||||||||
| 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 alle Reihenfolgen der Einfügung nach dem AVL-Einfügealgorithmus mit demselben Gewicht versehen. (Deshalb summieren die Häufigkeiten zu n! auf.) Der große Unterschied zwischen minimaler und maximaler Häufigkeit resp. zeigt, dass die entstehenden Baumformen sehr unterschiedlich häufig sind, wobei die häufigsten gleichzeitig minimale externe Pfadlänge haben. Letzteres ist gleichzeitig Bezugspunkt für die mittlere Verlängerung der externen Pfadlänge vn. Fibonacci-Bäume sind durchaus selten, haben aber nicht notwendigerweise maximale externe Pfadlänge .
Diese Häufigkeiten sind wesentlich schwerer zu berechnen als die obigen Baumanzahlen und Verlängerungen der Pfadlänge vh, bei denen die AVL-Bäume einer festen Höhe als gleich wahrscheinlich angenommen werden. Für kleine Bäume unterscheiden sich vn und vh allerdings nur geringfügig. R. W. Floyd schätzt den mittleren Aufwand, unter Schlüsseln das Fehlen eines -ten festzustellen, auf , was asymptotisch einem Wert von für vn entspricht.
Die Spalten , und sind die Folgen A006265, A001855 resp. A228155 in OEIS.
Flankentiefe Bearbeiten
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 ist sie höchstens und mindestens
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 . Sei dazu die Anzahl der AVL-Bäume der Höhe mit linker Flankentiefe und rechter Flankentiefe . Dann ist
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 ist
Es ist dasselbe wie oben.
Die mittlere linke wie rechte Flankentiefe für einen AVL-Baum der Höhe ist dann
Zahlenwerte für kleine sind in Tabelle 1.
Mittlere Abstiegstiefe beim Löschen Bearbeiten
Ä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 entspricht ihr Mittelwert dem soeben berechneten dh.
Der Mittelwert über alle Knoten eines AVL-Baumes ist aber wesentlich niedriger, da die meisten Knoten auf geringer Höhe liegen. Sei dazu die Anzahl der AVL-Bäume der Höhe mit Knoten, linker Flankentiefe und Flankentiefensumme und rechter Flankentiefe und Flankentiefensumme . Dabei sei Flankentiefensumme die Summe aller linken resp. rechten Flankentiefen eines gegebenen Baums. Dann ist
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 mit Knoten und linker Flankentiefensumme ist
Diese Bäume haben damit pro Knoten die mittlere linke Flankentiefe . Die Flankentiefe gemittelt über alle AVL-Bäume der Höhe ist somit
Denn wir haben mit demselben 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 ebenfalls .
Einige Zahlenwerte:
| 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
Siehe auch Bearbeiten
Literatur Bearbeiten
- 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 Bearbeiten
- 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.
- external path length bei #Knuth a. a. O. pp. 399–400
- Bspw. hat der Fibonacci-Baum mit die externe Pfadlänge . Der AVL-Baum mit und 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