Fibonacci-Baum

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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-Baum der Stufe 5

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 | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

  • Alle internen Knoten haben den Balance-Wert –1.
  • Der Fibonacci-Baum der Stufe (mit ) hat die Höhe .
  • 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.
wobei die Höhe des Fibonacci-Baums ≥ 1 ist.
  • Damit lässt sich die Höhe in Abhängigkeit von der Knotenanzahl abschätzen zu
mit   ,     und  .

Suchtiefe[Bearbeiten | Quelltext 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 | Quelltext bearbeiten]

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

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[Bearbeiten | Quelltext 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:

(leerer Suchbaum)
(nur Wurzel)
(neue Wurzel) (linkes Kind) (rechtes Kind)
für h ≥ 2.

Dies wird befriedigt durch

.

Beweis:

.  ■

Die externe Pfadlänge[1], 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 über die mittlere Suchtiefe bei Fibonacci-Bäumen[2] 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.

Andere dünnste AVL-Bäume[Bearbeiten | Quelltext 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

a0 = 1
a1 = 1
ah = (ah–1ah–2) • 2   (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:[3]

A0 = 1
A1 = 1
Ah = (Ah–1Ah–2) • 2 + (Ah–1Ah–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 der Funktion

mit oder 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 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.

Anteil der unausgewogenen Knoten bei AVL-Bäumen[Bearbeiten | Quelltext 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

leerer Baum hat h=0, u=0, g=0
nur Wurzel hat h=1, u=0, 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 , 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 .

Flankentiefe[Bearbeiten | Quelltext 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

dh .

Zahlenwerte für kleine sind in Tabelle 1.

Mittlere Abstiegstiefe beim Löschen[Bearbeiten | Quelltext 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

AVL-Baum mit 1 Knoten
AVL-Baum mit 2 Knoten linkslastig
AVL-Baum mit 2 Knoten rechtslastig
AVL-Baum mit 3 Knoten
  
 
 

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:

dh
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

.

Mittlere Suchtiefe bei AVL-Bäumen[Bearbeiten | Quelltext bearbeiten]

Abschätzung mittels Rekursion über die Höhe[Bearbeiten | Quelltext 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

    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
,

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

nl und nr auf nl+nr =: n

und die externe Pfadlänge von

pl und pr auf 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 Anzahl
Bäume
Anteil
unausge-
wogene
Anzahl
externe
Blätter
externe
Pfadlä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 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 | Quelltext 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
hn Knoten Wurzeln pn vn
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 .[5]

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.[6] R. W. Floyd[7] 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.

Siehe auch[Bearbeiten | Quelltext bearbeiten]

Literatur[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. external path length bei #Knuth a. a. O. pp. 399-400
  2. In dieser Hinsicht sind nicht notwendigerweise die Fibonacci-Bäume am schlechtesten balanciert; bspw. gibt es einen AVL-Baum der Höhe 5 mit 20 Knoten (linkes Kind vollständig der Höhe 4, rechtes Kind Fibonacci der Höhe 3) und der externen Pfadlängensumme 97, wogegen der Fibonacci-Baum der Höhe 6 bei gleicher Knotenzahl nur auf 96 kommt.
  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.
  5. 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.
  6. Bei den Anteilen der Bäume mit unausgewogener Wurzel wird allerdings die unterschiedliche Gewichtung in extremer Form sichtbar.
  7. zitiert nach #Knuth a. a. O., S. 468