Suchbaum

Def.:

Ein binärer Suchbaum ist ein binärer Baum, bei dem alle Einträge im linken Teilbaum eines Knotens $x$ kleiner sind als der Eintrag im Knoten $x$ und bei dem alle Einträge im rechten Teilbaum eines Knotens $x$ größer sind als der Eintrag im Knoten $x$.

Der Aufwand aller Suchbaumoperationen ist proportional zur Anzahl der Knoten auf dem Wege von der Wurzel bis zu einem Blatt.

Best case:	Hat jeder Knoten 2 Söhne, so hat der Baum bei Höhe $h$
	$n = 2^{h} -1$ Knoten. Die Anzahl der Weg-Knoten ist $h = \log (n)$.
Worst case:	Werden die Elemente sortiert eingegeben, so entartet der Baum
	zur Liste, der Aufwand beträgt dann $O(n)$.
Average case:	Für $n$ zufällige Schlüssel beträgt der Aufwand $O(\log (n))$,
	genauer: Die Wege sind um 39 % länger als im best case.

Beispiel für einen binären Suchbaum

Damit die Algorithmen zur Navigation in einem Suchbaum für beliebige Objekte formuliert werden können, wird ein Interface Comparable verwendet, welches eine Methode compareTo ankündigt. Diese Methode muß von jedem Anwender bezogen auf die von ihm zu speichernden Objekte implementiert werden (z.B. als CharComparable oder StringComparable. Der Suchbaum wiederum implementiert ein Interface Menge, welches die grundsätzlichen Methoden zum Verwalten einer Menge von Objekten ankündigt: lookup, insert und delete.

In den folgenden drei Grafiken wird mit einem gefüllten Kreis der NULL-Zeiger visualisiert und mit einem gefüllten Quadrat der Verweis auf einen leeren Baum (bestehend aus einem Knoten mit drei Nullzeigern).

Sei $x$ das Element in dem zu löschenden Knoten des Suchbaums.

Löschen eines Knotens ohne Söhne

Löschen eines Knotens mit einem Sohn

Löschen eines Knotens mit zwei Söhnen

Source: Comparable.java     JavaDoc: Comparable.html    

Source: CharComparable.java     JavaDoc: CharComparable.html    

Source: StringComparable.java     JavaDoc: StringComparable.html    

Source: Menge.java     JavaDoc: Menge.html    

Source: SuchBaum.java     JavaDoc: SuchBaum.html    

Source: SuchBaumTest.java     JavaDoc: SuchBaumTest.html     Applet:

Abhängigkeiten

Folgende Grafik verdeutlicht die Abhängigkeiten der zum Suchen von Characters verwendeten Module:

Multimenge

Zur Verwaltung einer Multimenge (Elemente sind ggf. mehrfach vorhanden) kann ein Suchbaum wie folgt verwendet werden:

1. Möglichkeit:

Elemente doppelt halten

2. Möglichkeit:

Zähler im Knoten mitführen

Beim Einfügen:

Zähler hochzählen, sofern Element schon vorhanden, sonst einfügen.

Beim Löschen:

Zähler herunterzählen, sofern mehrfach da, sonst entfernen.