Baumstruktur

Eine Baumstruktur, oft einfach Baum genannt, ist in der Informatik eine hierarchische Datenstruktur. Sie besteht aus Knoten (Nodes), die durch gerichtete Kanten verbunden sind. Es gibt einen besonderen Wurzelknoten (Root), von dem aus Beziehungen zu Kindknoten verlaufen. Jeder Knoten (außer dem Root) hat genau einen Elternknoten. Knoten können null oder mehr Kinder haben. Es gilt: Es gibt genau einen Pfad zwischen zwei Knoten, und es entsteht eine baumartige Hierarchie; ein Zyklus ist nicht erlaubt.

In der Praxis werden Bäume als gerichtete, azyklische Graphen modelliert; in der Graphentheorie spricht man meist von gerichteten Bäumen; in vielen Anwendungen auch von Wäldern, wenn mehrere Bäume gleichzeitig existieren.

Typen: Es gibt Wurzelbäume, Binärbäume, mehrstellige Bäume (K-ary, variable Kindzahl). Binäre Suchbäume ordnen die Schlüssel so, dass linkes Kind kleiner, rechtes Kind größer ist; selbstbalancierende Varianten wie AVL- oder Rot-Schwarz-Bäume sichern eine bestimmte Höhe. Allgemeine Bäume haben keine Ordnungsbedingung.

Operationen und Traversierungen: Tiefensuche (Preorder, Inorder, Postorder) und Breitensuche (Level-order). Einfügen, Entfernen, Umstrukturieren betreffen meist Subbäume. Komplexitäten hängen von der Implementierung ab, z. B. Suchen in ausgewogenen Bäumen O(log n), in ungeordneten Bäumen O(n).

Anwendungen: Dateisysteme, DOM in Webbrowsern, Syntaxbäume in Compilern, Organisationsstrukturen, Taxonomien und XML-/HTML-Strukturen.

Darstellung: Bäume werden durch Verweise/Zeiger implementiert. In Arrays können vollständige Bäume (wie Heaps) gespeichert werden. Speicherbedarf entspricht O(n).