Bäume

Bäume gehören zu den wichtigsten Datenstrukturen.

Es gibt sie in sehr vielen Varianten, wovon wir nur einige im Rahmen dieser Vorlesung kennenlernen werden.

Eine allgemeine Definition von Bäumen nach Knuth:
Ein Baum ist eine endliche Menge T von einem oder mehreren Knoten, so daß

es einen speziell ausgezeichnenten Knoten gibt, der als Wurzel bezeichnet wird: root(T); und

die verbleibenden Knoten (ohne die Wurzel) in m 0 disjunkte Mengen T₁, ..., T_m aufgeteilt sind, wobei jede dieser Mengen wiederum ein Baum ist. Die Bäume T₁, ..., T_m werden die Unterbäume der Wurzel genannt.

Diese Definition ist rekursiv. Allerdings ist es kein Zirkelschluß, da die Gesamtmenge der Knoten endlich ist und sich die Menge der Knoten bei jedem Rekursionsschritt um mindestens eins vermindert, so daß am Ende Bäume mit nur einem Knoten verbleiben.

Bäume lassen sich auch nicht-rekursiv definieren, jedoch paßt Rekursion zur Natur der Bäume, da viele Algorithmen auf Bäumen rekursiv arbeiten.

Hinweis: Diese Seite und die folgenden lehnen sich sehr eng an das Kapitel 2.3 von ``The Art of Computer Programming'', Band 1, von Donald E. Knuth an. Insbesondere wurden auch einige Abbildungen mehr oder weniger direkt übernommen.