Binärbaum: Aufbau, Traversierung und Suchbaum

Ein Baum besteht aus Knoten und Kanten. Eine Kante verbindet zwei Knoten und zeigt, dass zwischen ihnen eine Beziehung besteht. Ein Knoten kann einen Namen tragen, den Schlüssel.

Die Wurzel ist der einzige Knoten, in den keine Kante hineinführt. Jeder andere Knoten hängt durch genau eine eingehende Kante an einem anderen Knoten. Dieser Knoten ist sein Elternteil, der hängende Knoten ist sein Kind. Hat ein Knoten keine Kinder, heißt er Blatt. In Zeichnungen steht die Wurzel meist oben und die Blätter stehen unten.

Im Binärbaum hat jeder Knoten höchstens zwei Kinder. Meist verlangt man, dass sich die Kinder eindeutig in ein linkes und ein rechtes Kind einteilen lassen.

Ein Teilbaum besteht aus einem Knoten und allen seinen Nachkommen und ist selbst ein Baum. Die Kinder eines Knotens sind die Wurzeln von Teilbäumen.

Beispiel: Die Schlüssel 50, 30, 20, 70, 40, 80, 60 werden in dieser Reihenfolge in einen leeren Suchbaum eingefügt. 50 ist die Wurzel. 30 ist das linke und 70 das rechte Kind von 50. 20 ist das linke und 40 das rechte Kind von 30. 60 ist das linke und 80 das rechte Kind von 70. Die Blätter sind 20, 40, 60 und 80. Der Teilbaum mit der Wurzel 30 besteht aus 30, 20 und 40.

Die Tiefe eines Knotens ist die Zahl der Kanten bis zur Wurzel. Die Wurzel hat die Tiefe 0. Knoten mit gleicher Tiefe bilden eine Ebene (ein Niveau). Tiefe ist eine Eigenschaft eines Knotens, Höhe eine des ganzen Baums.

Für die Höhe gibt es zwei Zählweisen. In Zählweise A ist die Höhe die größte vorkommende Tiefe eines Knotens. In Zählweise B setzt man die Höhe um eins höher. Dann hat der leere Baum die Höhe 0 und der Baum nur aus der Wurzel die Höhe 1. Die Höhe ist dann die Maximalzahl der Knotenebenen. Lies deshalb in einer Aufgabe zuerst, welche Zählweise gilt.

Beispiel: Die Schlüssel 5, 2, 8, 1, 4, 6, 9, 0, 3, 7 werden in dieser Reihenfolge in einen leeren Suchbaum eingefügt. Die Tabelle zeigt die Tiefen. Die größte Tiefe ist 3, also ist die Höhe in Zählweise A gleich 3. Der Baum hat 4 Ebenen, also ist die Höhe in Zählweise B gleich 4.

Traversieren heißt, die Knoten eines Baums systematisch in einer bestimmten Reihenfolge zu untersuchen. Üblich ist, den linken Teilbaum vor dem rechten zu durchlaufen. Die Regeln gelten rekursiv: In jedem Teilbaum gilt wieder dieselbe Regel.

Preorder (Knoten, links, rechts): Erst kommt der Knoten, dann der linke und dann der rechte Teilbaum. Inorder (links, Knoten, rechts): Erst der linke Teilbaum, dann der Knoten, dann der rechte Teilbaum. Postorder (links, rechts, Knoten): Erst der linke, dann der rechte Teilbaum, zuletzt der Knoten.

Bei der Level-order beginnst du an der Wurzel und durchläufst die Ebenen von links nach rechts.

Bei einem binären Suchbaum entspricht die Inorder-Reihenfolge der Anordnung der Schlüssel. Du bekommst sie also sortiert.

Ein binärer Suchbaum ist ein Binärbaum, dessen Knoten Schlüssel tragen. Die Schlüssel des linken Teilbaums eines Knotens sind nur kleiner (oder gleich), die des rechten Teilbaums nur größer (oder gleich) als der Schlüssel des Knotens selbst. In unseren Beispielen kommen keine doppelten Schlüssel vor.

So suchst du: Vergleiche den Suchschlüssel zuerst mit dem Schlüssel der Wurzel. Sind beide gleich, ist der Eintrag gefunden. Ist der Suchschlüssel kleiner, geht die Suche im linken Teilbaum weiter, ist er größer, im rechten. Fehlt dieser Teilbaum, gibt es den Eintrag nicht im Baum.

Die Suche folgt einem Weg ab der Wurzel, höchstens bis zu einem Blatt. Ihre Zeit hängt im Mittel und im schlechtesten Fall linear von der Höhe des Baums ab.

Beim Einfügen orientierst du dich an der Suche. Du vergleichst den neuen Schlüssel mit der Wurzel. Ist er größer, schaust du, ob die Wurzel ein rechtes Kind hat. Wenn nicht, hängst du ihn dort an. Sonst gehst du zu diesem Kind und wiederholst das. Bei einem kleineren Schlüssel gehst du entsprechend nach links. Der letzte Knoten einer erfolglosen Suche bildet zusammen mit der letzten Vergleichsrichtung den Einfügepunkt. Nach dem Einfügen ist das neue Element ein Blatt.

Fügt man aufsteigend (oder absteigend) sortierte Schlüssel nacheinander ein, kann der Baum entarten: Er wird zu einer linearen Liste, also zu einer Kette. Bei 1, 2, 3, 4, 5 wird jeder neue Schlüssel rechtes Kind des vorherigen. Hat im entarteten Baum jeder Knoten nur ein Kind, kommt die Suche einer sequentiellen Suche gleich. Dabei muss man den Suchschlüssel unter Umständen mit allen Schlüsseln vergleichen. Höhen-balancierte Suchbäume ermöglichen die Suche in garantiert logarithmischer Laufzeit.