Das Kefk Network Wiki befindet sich im Testbetrieb.

---

Aus Kefk.

Ein Fibonacci-Baum ist eine Datenstruktur in der Informatik. Er stellt einen Spezialfall eines AVL-Baums dar. Der Name deutet an, dass Fibonacci-Bäume analog zu den Fibonacci-Zahlen rekursiv definiert sind.

Löscht man einen beliebigen Knoten eines Fibonacci–Baums, so sinkt die Knotenzahl unter das Minimum, das für die entsprechende bisherige Baumhöhe galt. Dies bedeutet, dass es auf jeden Fall zu einer Höhenverminderung kommt, entweder durch Blattlöschung (z.B. der 1 im Beispiel unten) oder durch Entstehen von Störstellen und ein oder mehrerer anschliessender Rotationen.

Im Prinzip kann es beim Löschen dazu kommen, dass eine Rotation zur Behebung einer Störstelle, in der darüberliegenden Ebene eine neue Störstelle verursacht. Da die Höhe im AVL–Baum logarithmisch zur Knotenzahl n ist, kann also auch log(n) mal eine Rotation erforderlich sein. Die Rotationsoperationen selbst lassen sich in konstantem Aufwand ausführen, womit sich insgesamt als Komplexität für das Löschen im AVL–Baum wiederum log(n) ergibt.

Die Basis des Logarithmus ist wie bei den Fibonacci–Zahlen die Zahl des goldenen Schnittes und damit ca. 1,61. Idealerweise ist für einen Binärbaum natürlich die Basis 2, die Gewährleistung schärferer Balancierungskriterien als der Höhenausgeglichenheit ist aber so aufwendig, dass im Mittel die Operationen für solche Bäume aufwendiger sind.

Rekursive Definition

• 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 n (mit n ≥ 2) besteht aus einer Wurzel, deren linker Sohn ein Fibonacci-Baum der Stufe n - 1 und deren rechter Sohn ein Fibonacci-Baum der Stufe n - 2 ist.

Eigenschaften

• Der Fibonacci-Baum der Stufe n (mit n > 0) hat die Höhe n - 1.

• Ist k_n die Anzahl der Knoten des Fibonacci-Baums der Stufe n, dann gilt

  k₀ = 0

  k₁ = 1

  k_n = 1 + k_{n - 1} + k_{n - 2} (n ≥ 2)

• Ist b_n die Anzahl der Blattknoten des Fibonacci-Baums der Stufe n, dann gilt

  b₀ = 0

  b₁ = 1

  b_n = b_{n - 1} + b_{n - 2} (n ≥ 2)

• Mit Hilfe der Bezeichnung f_n für die n-te Fibonacci-Zahl lassen sich diese Größen auch so ausdrücken:

  k_n = f_{n + 2} - 1

  b_n = f_n

• Zu einer gegebenen Höhe entspricht ein Fibonacci-Baum einem AVL-Baum mit minimaler Knotenanzahl, er ist also am schlechtesten ausgeglichen.

Siehe auch

Fibonacci-Heap

Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort Fibonacci-Baum, die Liste der bisherigen Autoren befindet sich in der Versionsliste; die Originalfassung kann dort auch bearbeitet werden. Alle Texte der Wikipedia und ihre Derivate stehen unter der GNU-Lizenz für freie Dokumentation.