Bäume begegnen uns in vielfältigen Alltagssituationen ohne, dass wir so direkt damit Bäume in Verbindung bringen.
Einige Beispiele:
Die einzelnen Elemente einer Baumstruktur werden Knoten genannt. Die Knoten sind durch Kanten (Verbindungspfeile) verbunden. Es gibt besondere Knoten: Der Anfangsknoten aller Suchpfade im Suchbaum heißt Wurzel des Baums. Knoten können einen oder zwei Nachfolgeknoten haben. Die Nachfolgeknoten heißen Nachfolger oder Söhne des Knotens, der Vorgänger eines Knotens heißt Vorgänger oder Vater des Knotens. Jeder Knoten besitzt entweder zwei oder einen oder keinen Nachfolger. Ein Knoten, der keinen Nachfolger besitzt, heißt Blatt. Ein Knoten, der keine Wurzel und kein Blatt ist, heißt innerer Knoten. Die maximale Anzahl der Nachfolgeknoten heißt Grad der Baumstruktur.
Unter einem (gerichteten) Baum wollen wir folgendes verstehen:
Eine Baumstruktur (kurz: Baum) vom Grad 2 heißt Binärbaum. Jeder Knoten eines Binärbaums hat maximal 2 Nachfolger.
Beispiel:
Wir wollen nun in einen Binärbaum Daten eintragen. Wir nehmen dazu eine Liste von 12 Zahlen: [7, 12, 0, 5, 9, 3, 8, 2, 13, 10, 15, 1]. Der Baum braucht 12 Knoten, die wir „zeilenweise von links nach rechts“ auffüllen. Der Baum hat dann die folgende Gestalt:
Die Zahlen in den Kreisen sind die in den Knoten eingetragenen Werte, die Zahlen neben den Kreisen geben die Reichenfolge an, in der die Daten eingetragen wurden.
Ein Binärbaum heißt binärer Suchbaum oder kurz Suchbaum, wenn die Knoten bezüglich eines Vergleichskriteriums geordnet sind.
Wir können die Zahlen aus der Liste [7, 12, 0, 5, 9, 3, 8, 2, 13, 10, 15, 1] auch nach der folgenden Regel in den Baum eintragen: Der erste Wert kommt in die Wurzel. Der Wert des nächsten Listenelements wird mit dem in der Wurzel eingetragenen vergleichen. Ist er kleiner, wird ein 'linker Sohn' erzeugt und der Wert dort abgelegt. Andernfalls, erzeugen wir einen 'rechten Sohn' in dem wir unseren Wert ablegen. Ist der Knoten, wo man eintragen will schon belegt, vergleicht man ihn mit den einzutragenden Wert auf die bereits beschriebene Weise und steigt somit den Baum solang herunter, bis der eigentliche Eintrag erfolgen kann. So werden nacheinander alle Elemente der Liste abgearbeitet. Das Bild unten zeigt den fertigen Baum
Baum heißt binärer Suchbaum
B ist leer oder
Wenn B nicht leer ist gilt
der rechte und der linke Unterbaum von B ebenfalls binäre Suchbäume sind oder
wenn w der Wert in der Wurzel ist, sind alle Werte in den Knoten des linken Unterbaums kleiner als w und die Werte aller Knoten des rechten Unterbaums größer als w. Dabei kommt also jeder Wert nur einmal in einem Binären-Such-Baum vor, außer man ersetzt die Relation größer durch größer gleich.
© Ralph-Erich Hildebrandt, 09. Mai 2005