Gewurzelter Baum


Gewurzelter Baum
Gewurzelter Baum als In-Tree mit Knoten 2 als Wurzel.

Ein gewurzelter Baum (auch Wurzelbaum oder Arboreszenz) ist in der Graphentheorie ein Baum, dessen Kanten eine ausgezeichnete Richtung besitzen, so dass im Gegensatz zum ungerichteten Baum ein Knoten als Wurzel identifiziert werden kann. Es lassen sich Out-Trees, bei denen die Kanten von der Wurzel ausgehen, und In-Trees, bei denen die Kanten in Richtung Wurzel zeigen, unterscheiden.

Definition

Gewurzelte Bäume sind gerichtete Graphen 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 bezeichnet man als Blätter. Als Tiefe eines Knotens bezeichnet man die Länge des Pfades von der Wurzel zu ihm und als Höhe des Baumes die Länge eines längsten Pfades, der immer von der Wurzel zu einem Blatt laufen muss. Im Falle von In-Trees bezeichnet man den maximalen Eingangsgrad des Baumes als seine Ordnung und alle Knoten mit Eingangsgrad 0 als Blätter. Als Höhe des Baumes bezeichnet man auch hier die Länge eines längsten Pfades, der immer von einem Blatt zur Wurzel laufen muss.

Wie bei ungerichteten Bäumen bezeichnet man auch in gewurzelten Bäumen alle Knoten, die kein Blatt sind, als innere Knoten. Manchmal schließt man die Wurzel dabei aber aus.

Für Out-Trees gibt es noch eine ganze Reihe weiterer Begriffe. Für einen von der Wurzel verschiedenen Knoten v bezeichnet man den Knoten, durch den er mit einer eingehenden Kante verbunden ist als Vater, Vaterknoten, Mutter, Mutterknoten, Elternknoten oder Vorgänger von v. Als Vorfahren von v werden alle Knoten auf dem Pfad zur Wurzel bezeichnet.

Umgekehrt bezeichnet man alle Knoten, die von einem beliebigen Knoten v aus durch eine ausgehende Kante verbunden sind als Kinder, Kinderknoten, Sohn oder Nachfolger von v. Als Nachfahren von v bezeichnet man alle Knoten zu denen von v aus ein Pfad existiert, also alle Knoten des Unterbaums, der v als Wurzel hat. Als Geschwister oder Geschwisterknoten werden in einem Out-Tree Knoten bezeichnet, die den gleichen Vorgängerknoten 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.


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Baum (Datenstruktur) — Ein Baum ist in der Graphentheorie ein spezieller Graph, mit dem sich eine Monohierarchie modellieren lässt. Je nachdem, ob die Kanten des Baums eine ausgezeichnete Richtung besitzen, lassen sich graphentheoretische Bäume unterteilen in… …   Deutsch Wikipedia

  • Baum (Informatik) — Ein Baum ist in der Graphentheorie ein spezieller Graph, mit dem sich eine Monohierarchie modellieren lässt. Je nachdem, ob die Kanten des Baums eine ausgezeichnete Richtung besitzen, lassen sich graphentheoretische Bäume unterteilen in… …   Deutsch Wikipedia

  • Gerichteter Baum — Gewurzelter Baum als In Tree mit Knoten 2 als Wurzel. Ein gewurzelter Baum (auch Wurzelbaum oder Aboreszenz) ist in der Graphentheorie ein Baum, dessen Kanten eine ausgezeichnete Richtung besitzen, so dass im Gegensatz zum ungerichteten Baum ein… …   Deutsch Wikipedia

  • Binärer Baum — Ein voller, aber nicht vollständiger Binärbaum Als Binärbaum bezeichnet man in der Graphentheorie eine spezielle Form eines Graphen. Genauer gesagt handelt es sich um einen gewurzelten Baum, bei dem jeder Knoten höchstens zwei Kindknoten besitzt …   Deutsch Wikipedia

  • Phylogenetischer Baum — basierend auf rRNA Genen Ein phylogenetischer Baum ist ein Baum, der die evolutionären Beziehungen zwischen verschiedenen Arten oder anderen Einheiten, von denen man vermutet, dass sie einen gemeinsamen Vorfahren besitzen, darstellt. Damit ist… …   Deutsch Wikipedia

  • Wurzelbaum — Gewurzelter Baum als In Tree mit Knoten 2 als Wurzel. Ein gewurzelter Baum (auch Wurzelbaum oder Aboreszenz) ist in der Graphentheorie ein Baum, dessen Kanten eine ausgezeichnete Richtung besitzen, so dass im Gegensatz zum ungerichteten Baum ein… …   Deutsch Wikipedia

  • Glossar Graphentheorie — Dieser Artikel wurde auf der Qualitätssicherungsseite des Portals Mathematik zur Löschung vorgeschlagen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Mathematik auf ein akzeptables Niveau zu bringen. Dabei werden Artikel… …   Deutsch Wikipedia

  • Oktalbaum — Ein Octree (von lat. oct „acht“, und engl. tree „Baum“) ist eine Datenstruktur der Informatik. Ein Octree ist ein gewurzelter Baum, dessen Knoten jeweils entweder acht direkte Nachfolger oder gar keine Nachfolger haben. Octrees werden… …   Deutsch Wikipedia

  • Binary Tree — Ein voller, aber nicht vollständiger Binärbaum Als Binärbaum bezeichnet man in der Graphentheorie eine spezielle Form eines Graphen. Genauer gesagt handelt es sich um einen gewurzelten Baum, bei dem jeder Knoten höchstens zwei Kindknoten besitzt …   Deutsch Wikipedia

  • Binäre Bäume — Ein voller, aber nicht vollständiger Binärbaum Als Binärbaum bezeichnet man in der Graphentheorie eine spezielle Form eines Graphen. Genauer gesagt handelt es sich um einen gewurzelten Baum, bei dem jeder Knoten höchstens zwei Kindknoten besitzt …   Deutsch Wikipedia