Unterbäume

Unterbäume sind Teilbäume in der Graphentheorie und Informatik. Ein Baum ist ein zusammenhängender, azyklischer Graph. Ein Unterbaum bezeichnet allgemein eine Teilmenge von Knoten und Kanten, die einen Baum bildet und damit die Struktur des Baumes bewahrt.

In wurzelten Bäumen besteht der Unterbaum, der an einem Knoten v beginnt, aus diesem Knoten und allen seinen Nachkommen. Formal: Sei T=(V,E) ein wurzliger Baum mit Wurzel r. Der Unterbaum von v∈V umfasst alle Knoten, die von v aus durch eine Folge von Kindkanten erreichbar sind, sowie die zugehörigen Kanten. Der Unterbaum ist durch seine Wurzel eindeutig bestimmt.

In ungerichteten Bäumen ist ein Unterbaum jeder zusammenhängende Teilgraph, der wiederum ein Baum ist. Er entsteht durch eine geeignete Teilmenge U⊆V von Knoten und die zugehörigen Kanten E[U], sodass der Untergraph (U,E[U]) zusammenhängend und azyklisch bleibt.

Eigenschaften und Anwendungen: Die Größe oder andere Aggregationen über die Knoten eines Unterbaums lassen sich oft effizient berechnen, etwa mit Tiefensuche (DFS) oder mit der Euler-Tour-Technik. In Datenstrukturen dienen Unterbäume als Grundlage für Operationen wie Subtree-Updates oder Subtree-Abfragen; Beispiele sind Segmentbäume oder Baumbasen in Baumschnitt-Algorithmen. Unterbäume treten außerdem in Ausdrucksbäumen, Dateisystemen und syntaktischen Bäumen auf.

Siehe auch: Baum, Wurzelbaum, Segmentbaum, Euler-Tour.