Wurzelbäume in der Graphentheorie

1. Was ist ein Wurzelbaum?

In der Graphentheorie ist ein Baum ein zusammenhängender Graph ohne Zyklen. Ein Wurzelbaum ist einfach ein Baum, in dem ein besonderer Knoten als Wurzel gewählt wurde. Diese eine Wahl gibt jedem anderen Knoten ein klares „Oben" (zur Wurzel hin) und „Unten" (von ihr weg) und macht aus einem schlichten Baum eine Hierarchie.

Eine nützliche Tatsache: Ein Baum mit n Knoten hat immer genau n - 1 Kanten, und zwischen je zwei Knoten gibt es genau einen Pfad — nicht mehr und nicht weniger.

2. Wichtige Begriffe

• Wurzel: der oberste Knoten; der einzige ohne Elternknoten.
• Eltern / Kind: verbindet eine Kante A (näher an der Wurzel) mit B, so ist A der Elternknoten und B das Kind.
• Geschwister: Knoten mit demselben Elternknoten.
• Blatt: ein Knoten ohne Kinder — ein „Ende" des Baums.
• Innerer Knoten: jeder Knoten mit mindestens einem Kind.
• Vorfahr / Nachfahr: Knoten auf dem Pfad zur Wurzel hinauf / von einem Knoten hinab.
• Tiefe: die Anzahl der Kanten von der Wurzel zu einem Knoten. Die Wurzel hat Tiefe 0.
• Höhe: die längste Distanz von einem Knoten hinab zu einem Blatt. Die Höhe des Baums ist die Höhe seiner Wurzel.
• Teilbaum: ein Knoten zusammen mit all seinen Nachfahren.

3. Mit und ohne Wurzel

Ein ungewurzelter Baum beschreibt nur, welche Knoten verbunden sind — es gibt kein Oben oder Unten. Sobald man eine Wurzel wählt, erhält dieselbe Kantenmenge eine Richtung: Kanten werden nun als von der Wurzel weg gerichtet verstanden, sodass sich ein Wurzelbaum wie eine besondere Art gerichteter Graph verhält. Eine andere Wurzel erzeugt aus demselben zugrunde liegenden Baum eine andere Hierarchie.

4. Wie Wurzelbäume dargestellt werden

Es gibt drei gängige Wege, einen Wurzelbaum im Code zu speichern:

• Eltern-Array: speichert den Elternknoten jedes Knotens in einem Array (parent[i]). Kompakt und ideal, um „zur Wurzel hinaufzulaufen".
• Kinderlisten: jeder Knoten hält eine Liste seiner Kinder — die flexibelste Darstellung für Traversierungen.
• Linkes-Kind / rechter-Bruder: eine binärartige Kodierung, die jeden n-ären Baum mit nur zwei Zeigern pro Knoten speichert.

5. Typen von Wurzelbäumen

• Binärbaum: jeder Knoten hat höchstens zwei Kinder, ein „linkes" und ein „rechtes".
• Binärer Suchbaum (BST): ein sortiert gehaltener Binärbaum, sodass Suchvorgänge im ausgeglichenen Fall O(log n) dauern.
• N-ärer Baum: Knoten dürfen beliebig viele Kinder haben — wie ein Ordner im Dateisystem.
• Ausgeglichene Bäume (AVL, Rot-Schwarz, B-Bäume) halten ihre Höhe automatisch klein, um schnelle Operationen zu garantieren.

6. Einen Wurzelbaum traversieren

Alle Knoten zu besuchen heißt Traversierung, und es gibt zwei große Familien:

• Tiefensuche (DFS): so tief wie möglich gehen, bevor man zurückgeht. Bei Binärbäumen gibt es die Varianten Preorder, Inorder und Postorder.
• Breitensuche (BFS): alle Knoten einer Ebene besuchen, bevor man tiefer geht — auch ebenenweise Traversierung genannt.

Falls Ihnen das bekannt vorkommt: Es sind dieselben Strategien wie bei allgemeinen Graphen. Siehe unsere ausführliche Analyse zu BFS vs DFS.

7. Praktische Anwendungen

• Dateisysteme: Ordner und Dateien bilden einen Wurzelbaum mit dem Wurzelverzeichnis an der Spitze.
• Das HTML-DOM: jede Webseite ist ein Wurzelbaum aus Elementen — auch die, die Sie gerade lesen.
• Datenbanken: B-Bäume und B+-Bäume treiben die Indizes an, die Abfragen schnell machen.
• Compiler: Quellcode wird in einen abstrakten Syntaxbaum (AST) geparst.
• Entscheidungsbäume und Heaps: Machine-Learning-Modelle und Prioritätswarteschlangen beruhen beide auf Wurzelbäumen.