Metraipolis › archive › dc_020e3bc2f599

Fibonacci-Baum — Wikipedia (de)

Source
Wikipedia (de)
Original
https://de.wikipedia.org/wiki/Fibonacci-Baum
License (as archived)
CC-BY-SA-4.0
Archived
2026-11-06T23:14:00.763Z
SHA-256 of the archived text
b54181a43aa7d9aef7e9fe654d289e220c3f1ffdeb7fe4918cda42494dfdf33e
Stable URL of this page
https://metraipolis.com/documento/dc_020e3bc2f599

How to cite

Fibonacci-Baum — Wikipedia (de) — Wikipedia (de), https://de.wikipedia.org/wiki/Fibonacci-Baum (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_020e3bc2f599 (Metraipolis archive dc_020e3bc2f599, sha256 b54181a43aa7d9aef7e9fe654d289e220c3f1ffdeb7fe4918cda42494dfdf33e)
BibTeX
@misc{dc020e3bc2f599,
  title = {Fibonacci-Baum — Wikipedia (de)},
  howpublished = {Wikipedia (de)},
  url = {https://de.wikipedia.org/wiki/Fibonacci-Baum},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_020e3bc2f599; sha256 b54181a43aa7d9aef7e9fe654d289e220c3f1ffdeb7fe4918cda42494dfdf33e},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (de), https://de.wikipedia.org/wiki/Fibonacci-Baum. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 Φ:=1+52≈1,618034 des goldenen Schnittes. Ideal wäre für einen Binärbaum natürlich die Basis 2, 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.

Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in tedesco, in ordine alfabetico).
Fonte: Wikipedia in tedesco, voce «Fibonacci-Baum» — https://de.wikipedia.org/wiki/Fibonacci-Baum
Wikidata Q1410726: «variant of a binary tree where a tree of order n (n>1) has a left subtree of order n-1 and a right subtree of order n-2» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q1410726
Autori: i contributori di Wikipedia (cronologia: https://de.wikipedia.org/wiki/Fibonacci-Baum?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 265881296, consultata il 2026-11-06T23:10:23.195Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 22fc2d1e78b35a70138a48a0dad6a655c12f8dd73b7e7b9ec32497d89686c5f4