Baumdatenstrukturen

Baumdatenstrukturen sind hierarchische Datenstrukturen, die aus Knoten und Kanten bestehen, wobei ein Wurzelknoten den Stamm bildet. Jede Kante verbindet einen Elternknoten mit einem Kindknoten. In einem Baum existiert kein Zyklus; er ist azyklisch, und er ist üblicherweise zusammenhängend. In Wurzelbäumen hat jeder Knoten außer der Wurzel genau ein Elternteil; die Anzahl der Kanten beträgt n−1.

Wichtige Begriffe sind Wurzel, Knoten, Blätter, innere Knoten, Teilbaum, Tiefe und Höhe. Traversierungen umfassen Preorder, Inorder, Postorder sowie level-order (Breitensuche). Typische Repräsentationen sind pointerbasierte Verzweigungen, wobei jeder Knoten Verweise auf seine Kinder hält, oder arraybasierte Implementierungen, z. B. bei Heaps, wo Kindknoten durch Formeln adressiert werden.

Häufige Baumarten umfassen Binäre Bäume mit höchstens zwei Kindern pro Knoten, Binäre Suchbäume (BST), und balancierte Varianten wie AVL-Bäume oder Rot-Schwarz-Bäume. Heaps unterstützen Prioritätswarteschlangen; B-Bäume und B+-Bäume werden in Datenbanken genutzt; Trie-Strukturen dienen effizienten Wort- und Präfix-Suchen; Segment- und Fenwick-Bäume liefern Bereichsabfragen.

Operationen umfassen Einfügen, Suchen, Löschen, Balancieren sowie verschiedene Traversierungen. Anwendungen finden sich in Datenbanken, Dateisystemen, Compilerbau (Syntaxbäume), Informationsabruf und Prioritätswarteschlangen. Die Komplexität variiert: In ausgewogenen Bäumen liegen Such-, Einfüge- und Löschoperationen typischerweise bei O(log n); in unbalancierten BSTs können sie bis O(n) anwachsen. Baumdatenstrukturen modellieren logische Hierarchien und ermöglichen effizienten Zugriff auf Daten.