28.12 Was ist ein binärer Suchbaum?
 
  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
 

 

Einen Baum, den wir auf die beschriebene Weise erstellt haben, nennen wir einen binären Suchbaum. Die Definition eines binären Suchbaums lehnt sich sehr eng an die Definition eines binären Baums an. Ein binärer Baum heißt binärer Suchbaum

  • B ist leer oder
  • Wenn B nicht leer ist gilt
    • der rechte und der linke Unterbaum von B sind ebenfalls  binäre Suchbäume.
    • Ist w der Wert in der Wurzel, so sind alle Werte in den Knoten des linken Unterbaums kleiner als w und die Werte aller Knoten des rechten Unterbaums sind größer als w. (Insbesondere kommt also ein Wert nur einmal in einem Binären-Such-Baum vor, es sei denn, man ersetzt die Relation größer durch größer gleich.

Der Grund, warum wir einen solchen Baum Suchbaum nennen, liegt darin, dass das Auffinden eines Wertes in einem Suchbaum sehr effizient ist. Um einen Wert in unserem Baum aufzufinden, benötigen wir maximal 5 Vergleiche (= Höhe des Baumes = Anzahl der Kanten im längsten Pfad). In der Ausgangsliste waren es maximal 12. Noch effizienter gestaltet sich das Suchen, wenn der Baum ausgeglichen ist. Er ist ausgeglichen (AVL-Baum ; benannt nach Adelson, Velskii and Landis [1962]) wenn für jeden Knoten gilt, dass sich der linke und der rechte Teilbaum in ihren Höhen um maximal 1 unterscheiden. Wäre der Baum in unserem Beispiel ausgeglichen, so hätte er eine Tiefe von 3. Das Suchen in diesem Baum wäre somit auf 3 Vergleiche beschränkt.

Ob ein Baum, nachdem er aufgebaut wurde, ausgeglichen ist oder nicht, hängt davon ab, in welcher Reihenfolge die Werte in den Baum eingefügt werden. Dies soll an der Eingabe der drei Zahlen 1, 2 und 3 zeigen. Man kann sie auf mehrere Arten eingeben.

 
 

Eingabe: 1-2-3

Eingabe: 2-1-3

Eingabe: 3-1-2

 

Wie das erste Beispiel zeigt, erzeugt das Eingeben einer sortierten Liste einen extrem unausgeglichenen Baum, er hat dann nur linke oder nur rechte Kanten; der Baum wird im Extremfall zu einer Liste.

Es gibt Algorithmen, auf die wir nicht näher eingehen wollen, die es erlauben, aus einem nicht ausgeglichenen Baum einen ausgeglichenen zu machen.

Der Baum aus unserem Beispiel könnte nach einem solchen Verfahren z.B. in folgenden ausgeglichenen Baum überführt werden:

 
  Selbstverständlich lassen sich viele Arten von Daten in einen binären Suchbaum speichern, Voraussetzung allerdings ist, dass es in der Menge der einzutragenden Elemente eine Ordnungsrelation gibt, denn, wie wir gesehen haben, ohne Vergleich lässt sich nicht entscheiden, ob man beim Eintrag eines Wertes in einem linken oder einem rechten Teilbaum absteigen muss.
Bei der Ausgabe der Werte, die in einem Baum gespeichert sind, unterscheidet man drei Arten. Pre-Order, In-Order und Post-Order. Mit ihnen wollen wir uns im nächsten Abschnitt beschäftigen.

 
zu 28.13 Drei Ausgabenmodi eines Baumes
zur Startseite www.pohlig.de  (C) MPohlig 2004