![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/8/8c/Fibonacci_Tree_6.svg/langde-640px-Fibonacci_Tree_6.svg.png&w=640&q=50)
Fibonacci-Baum
Datenstruktur in der Informatik, Spezialfall des AVL-Baums / aus Wikipedia, der freien encyclopedia
Liebe Wikiwand-AI, fassen wir uns kurz, indem wir einfach diese Schlüsselfragen beantworten:
Können Sie die wichtigsten Fakten und Statistiken dazu auflisten Fibonacci-Baum?
Fass diesen Artikel für einen 10-Jährigen zusammen
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 :={\tfrac {1+{\sqrt {5}}}{2}}\approx 1{,}618034}
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.
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/8/8c/Fibonacci_Tree_6.svg/320px-Fibonacci_Tree_6.svg.png)
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.