Bäume
Bäume gehören zu den fundamentalen Datenstrukturen der Informatik. In Bäumen kann man nicht nur Daten, sondern auch relevante Beziehungen der Daten untereinander abbilden, wie Ordnungs- oder hierarchische Beziehungen.
Beispiele für Bäume
Es lassen sich viele hierarchische Strukturen finden, die als Baum dargestellt werden können. Dabei sind die Bäume, die wir hier betrachten, spezielle Formen von Graphen. Sie sind zyklenfrei (d.h. die Knoten bilden keinen Kreis innerhalb des Graphs) und haben einen eindeutigen „Einstiegspunkt“, die Wurzel des Baums.
Ein Familienstammbaum ist ein Beispiel für einen Binärbaum. Die Person, für den Stammbaum erstellt wurd, ist dabei die Wurzel des Baum, ihre Eltern die beiden Nachfolger des Knotens.
Das Document-Object Model einer HTML-Webseite kann sich als Baum angezeigt weren. Das folgende Bild zeigt eine Webseite und die Ansicht des DOM in den Entwicklertools im Browser:
Schematisch kann derselbe Baum folgendermaßen dargestellt werden:
Terminologie
Im Folgenden wollen wir uns anschauen, wie Bäume formal definiert werden können:
- Ein Baum besteht aus einer Menge von Knoten die untereinander durch Kanten verbunden sind. .
- Führt von Knoten A zu Knoten B eine Kante, dann ist A Vorgänger von B und B ist ein Kind von A.
- Ein Knoten ohne Kinder heißt Blatt.
- Es gibt genau einen Knoten ohne Elternknoten, dieser Knoten heißt Wurzel
- Jeder Knoten (bis auf die Wurzel) ist genau durch eine Kante mit seinem Vorknoten verbunden.
- Zwischen jedem Knoten und der Wurzel gibt es genau einen Pfad. Das bedeutet, dass ein Baum zusammenhängend ist und es keine Zyklen gibt.
- Jedem Baum lässt sich eine Tiefe zuordnen.
Binärbäume
Bei dem oben dargestellten Baum handelt es sich insbesondere um einen Binärbaum. Ein binärer Baum ist ein geordneter Baum, in dem jeder Knoten höchstens zwei Kinder hat.
Binärbäume eignen sich, um gesuchte Daten rasch wieder aufzufinden. Auf die Suche in Binärbäumen werden wir im Abschnitt Algorithmen noch einmal zurückkommen.