Suchen im binären Suchbaum

Die Inorder-Traversierung hat es verraten: Liegen die Werte geschickt im Baum, kommen sie sortiert heraus. Genau diese Ordnung macht das Suchen schnell.

• Binärer Suchbaum:Für jeden Knoten gilt: Alle Werte im linken Teilbaum sind kleiner, alle im rechten größer als der Wert der Wurzel.
• Kein Wert doppelt:Jeder Schlüssel kommt höchstens einmal vor.
• Suchen:x mit der Wurzel vergleichen — gleich: gefunden; kleiner: links weiter; größer: rechts weiter.
• Ende:Trifft die Suche auf einen leeren Baum, kommt x nicht vor.
• Suchpfad:Die Suche läuft nur einen Weg von der Wurzel nach unten — die anderen Teilbäume bleiben unberührt.

Suche die Zahl oben links: Klicke die Knoten in der Reihenfolge an, in der die Suche sie vergleicht (mit der Tastatur: Pfeiltasten und Enter). Endet die Suche erfolglos, klicke den leeren Baum an, bei dem sie aufhört. Der Zähler läuft mit.

Halte fest: Jeder Vergleich schließt einen ganzen Teilbaum aus. Die Suche braucht höchstens so viele Vergleiche, wie der Baum Ebenen hat.

Die vier Fälle der Merke-Box werden direkt zu einer rekursiven Methode — mit dem leeren Baum als Abbruch.

static boolean enthaelt(BinTree<Integer> b, int x) {
    if (b.isEmpty()) {
        return false;                          // leerer Baum: x fehlt
    }
    if (x == b.getItem()) {
        return true;                           // gefunden
    }
    if (x < b.getItem()) {
        return enthaelt(b.getLeft(), x);       // links weitersuchen
    }
    return enthaelt(b.getRight(), x);          // rechts weitersuchen
}
// Baum aus dem Applet: enthaelt(baum, 45) → true, enthaelt(baum, 81) → false

• Ohne Rekursion:Eine Schleife mit b = b.getLeft() bzw. b = b.getRight() läuft denselben Pfad hinab.
• Aufwand:höchstens h Vergleiche mit Knoten — h ist die Höhe des Baums.
• Ausgeglichen:Sind alle Ebenen bis auf die letzte voll, ist h so klein wie möglich.
• Entartet:Hat jeder Knoten nur ein Kind, ist der Baum eine Liste: h = n, die Suche wird linear.