Wurzelbäume in der Graphentheorie

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

Inhaltsverzeichnis

1. Was ist ein Wurzelbaum?
2. Wichtige Begriffe
3. Mit und ohne Wurzel
4. Wie sie dargestellt werden
5. Typen von Wurzelbäumen
6. Einen Wurzelbaum traversieren
7. Praktische Anwendungen

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.

Ein Wurzelbaum mit Wurzel A auf Tiefe 0, beschriftet mit Elternknoten und Kind, Geschwistern mit gemeinsamem Elternknoten, Blattknoten ohne Kinder, einem inneren Knoten, den Tiefenstufen 0 bis 3 und einer Höhe von 3 — Jeder Begriff in einem Bild: Die Wurzel liegt auf Tiefe 0, Kanten führen hinab zu den Kindern, Blätter (grün) haben keine Kinder, Geschwister teilen sich einen Elternknoten, und die Höhe des Baums ist sein längster Weg von der Wurzel zu einem Blatt.

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.

Derselbe Baum mit vier Kanten in drei Darstellungen: ohne Wurzel ohne Hierarchie, mit Wurzel P als lange Kette und mit Wurzel R als breite flache Hierarchie — Ein Baum ohne Wurzel, zwei verschiedene Wurzeln. Dieselben vier Kanten werden zu einer langen Kette, wenn P die Wurzel ist, und zu einer breiten, flachen Hierarchie, wenn R die Wurzel ist.

Bäume in Bewegung sehen

Bauen Sie einen Wurzelbaum und sehen Sie zu, wie DFS- und BFS-Traversierungen Knoten für Knoten aufleuchten. Tiefe, Höhe und Eltern-Kind-Beziehungen ergeben plötzlich Sinn.

Visualisierung öffnen

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.

Ein Binärbaum mit seinen vier Durchlaufreihenfolgen: Preorder, Inorder (die sortiert herauskommt), Postorder und Level-Order BFS — Die vier klassischen Durchläufe desselben Binärbaums. DFS gibt es als Preorder, Inorder und Postorder; BFS besucht Ebene für Ebene. Bei einem binären Suchbaum liefert Inorder die Knoten praktischerweise in sortierter Reihenfolge.

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.

Häufig gestellte Fragen

Was ist der Unterschied zwischen einem gewurzelten und einem ungewurzelten Baum?

Ein ungewurzelter Baum gibt nur an, welche Knoten verbunden sind. Ein Wurzelbaum bestimmt einen Knoten als Wurzel und verleiht dem Baum eine Hierarchie mit Eltern-Kind-Beziehungen und einer klaren Spitze.

Was ist der Unterschied zwischen Tiefe und Höhe eines Baums?

Die Tiefe ist die Distanz von der Wurzel zu einem bestimmten Knoten (die Wurzel hat Tiefe 0). Die Höhe ist die Distanz von einem Knoten zu seinem tiefsten Blatt; die Höhe des Baums ist die Höhe der Wurzel.

Ist ein Wurzelbaum ein gerichteter Graph?

Man kann ihn so auffassen. Sobald eine Wurzel gewählt ist, ist jede Kante implizit von der Wurzel weg gerichtet, sodass jeder Nicht-Wurzel-Knoten genau einen Elternknoten hat.

Wie viele Kanten hat ein Baum mit n Knoten?

Genau n - 1. Jede weitere Kante würde einen Zyklus erzeugen, den ein Baum per Definition nicht hat.