Baum (Graphentheorie)
Ein Baum ist in der Graphentheorie ein spezieller Graph. In der Informatik werden Bäume häufig als Datenstruktur eingesetzt. In diesem Fall werden sie aber anders repräsentiert als allgemeine Graphen. Es wird unterschieden in
- ungerichtete Bäume und
- gewurzelte Bäume, die weiter in
- Out-Trees und
- In-Trees
differenziert werden.
Durch Entfernen einer Kante zerfällt ein Baum in zwei Teilbäume und bildet damit einen Wald.
| Inhaltsverzeichnis |
Ungerichtete Bäume
Definitionen
Ungerichtete Bäume lassen sich durch folgende äquivalente Definitionen charakterisieren:Ein Baum ist ein einfacher Graph,
- der zusammenhängend und ohne Kreis ist oder
- in dem je zwei beliebige verschiedene Knoten durch genau einen Pfad verbunden sind oder
- der genau einen Knoten mehr als Kanten hat (#v=#e+1) und zusammenhängend ist oder
- der genau einen Knoten mehr als Kanten hat und kreisfrei ist oder
- der zusammenhängend ist und in dem durch Hinzunahme einer beliebigen neuen Kante ein Kreis entsteht.
Weitere Begriffe
In ungerichteten Bäumen gibt es im Gegengsatz zu gewurzelten Bäumen keine ausgezeichnete Wurzel. Es lassen sich lediglich Blätter identifizieren, die dadurch charakterisiert sind, dass sie nur genau einen Nachbarn besitzen, das heißt ihr Grad ist genau 1. Als Ordnung wird hier der Maximalgrad des Baumes bezeichnet. Alle Knoten, die keine Blätter sind, werden als innere Knoten bezeichnet.
Gewurzelte Bäume
Definition
ein gewurzelter Baum – auch Wurzelbaum genannt – ist ein gerichteter Graph mit einem ausgezeichneten Knoten, der so genannten Wurzel, für den gilt, dass im Falle von Out-Trees jeder Knoten durch genau einen gerichteten Pfad von diesem aus erreichbar ist oder dass im Falle von In-Trees dieser von jedem Knoten aus durch genau einen gerichteten Pfad erreichbar ist.
Weitere Begriffe
Im Falle von Out-Trees wird der maximale Ausgangsgrad als Ordnung des Baumes bezeichnet und alle Knoten mit Ausgangsgrad 0 werden Blätter genannt. Als Tiefe eines Knotens wird die Länge des Pfades von der Wurzel zu ihm hin und als Höhe des Baumes die Länge eines längsten Pfades bezeichnet. Im Falle von In-Trees wird der maximale Eingangsgrad des Baumes als seine Ordnung bezeichnet und alle Knoten mit Eingangsgrad 0 werden Blätter genannt. Die Höhe des Baumes ist auch hier die Länge eines längsten Pfades.
Wie bei ungerichteten Bäumen werden auch in gewurzelten Bäumen alle Knoten, die kein Blatt sind als innere Knoten bezeichnet. Manchmal schließt man die Wurzel dabei aber aus.
Der Teilbaum Te eines Knoten e in einem gewurzelten Baum T besteht aus e und allen Knoten, die Nachfolger von e sind, sowie den Kanten von T, die diese Knoten verbinden.
Für Out-Trees gibt es noch eine ganze Reihe weiterer Begriffe. Für einen von der Wurzel verschiedenen Knoten v wird der Knoten, durch den er mit einer eingehenden Kante verbunden ist als Elternknoten, Vorgänger, Vaterknoten oder kurz Vater von v bezeichnet. Als Vorfahren von v werden alle Knoten, die entweder Elternknoten von v oder Vorgänger des Elternknotens sind bezeichnet.
Umgekehrt werden alle Knoten, die von einem beliebigen Knoten v aus durch eine ausgehende Kante verbunden sind Kinderknoten, Kinder, Nachfolger oder Sohn von v genannt. Als Nachfahren von v werden Kinder von v oder deren Nachfahren bezeichnet. Als Geschwisterknoten oder kurz Geschwister werden in einem Out-Tree Knoten bezeichnet, die den gleichen Elternknoten besitzen.
Alternative Definition
Gewurzelte Bäume lassen sich auch rekursiv definieren. Sie bestehen aus einem Knoten w, der die Wurzel des Baumes darstellt, welcher ausschließlich mit den Wurzeln knotendisjunkter Bäume T1, T2, ..., Tn verbunden ist, bei Out-Trees in Richtung der Wurzeln von T1, T2, ..., Tn, wobei diese selbst Out-Trees sind und bei In-Trees in Richtung von w, wobei T1, T2, ..., Tn selbst In-Trees sind.
Spezielle Bäume
Es existiert eine Vielzahl von Begriffen, die Bäume näher spezifizieren. So gibt es zum Beispiel
Bäume als Datenstruktur
Gewurzelte Bäume, insbesondere Out-Trees, werden häufig als Datenstruktur verwendet. Bei beschränkter Ordnung können diese so implementiert werden, dass jeder Knoten einen festen Satz an Variablen oder ein Array für die Referenzen auf seine Kinder enthält. Häufig besitzen die Knoten auch eine Referenz auf ihren Elternknoten (back pointer).
Ein Baum unbeschränkter Ordnung kann implementiert werden, indem man statt Arrays dynamische Listen verwendet. In Programmiersprachen ohne dynamische Listen hat sich auch ein Verfahren bewährt, bei dem ein allgemeiner Baum durch einen Binärbaum implementiert wird:
center
Die rötliche Linie zeigt dabei den realisierten allgemeinen Baum, während die Pfeile die tatsächlichen Zeigerstrukturen repräsentieren. Das Grundprinzip besteht darin, dass ein Zeiger jeweils auf den am weitesten links stehenden Sohn zeigt, während der andere auf den rechten Bruder verweist. Hierbei ist zwar ein direkter Zugriff auf einzelne bestimmte Sohn-Knoten nicht mehr möglich, da man sich über die Geschwister voranarbeiten muss. Dafür ist diese Implementierung sehr speichereffizient.
Siehe auch: Wälder und Bäume in der Graphentheorie.