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$.

Beispiel für einen binären Suchbaum

Suchbaumoperationen

Die oben genannte Suchbaumeigenschaft erlaubt eine effiziente Umsetzung der Suchbaumoperationen lookup, insert und delete. lookup sucht nach einem gegebenen Objekt durch systematisches Absteigen in den jeweils zuständigen Teilbaum. insert sucht zunächst die Stelle im Baum, bei der das einzufügende Objekt platziert sein müsste und hängt es dann dort ein. delete sucht zunächst die Stelle, an der das zu löschende Objekt vermutet wird und klinkt es dann aus dem Baum aus. Je nach Zahl der Söhne ist dieser Vorgang unterschiedlich kompliziert (siehe nächste Seite).

Komplexität

Der Aufwand der Suchbaumoperationen ist jeweils proportional zur Anzahl der Knoten auf dem Wege von der Wurzel bis zu dem betroffenen Knoten.

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.

In den folgenden drei Grafiken wird mit einem schwarzen Punkt der null-Verweis visualisiert.

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

Um die Formulierung des Suchbaumalgorithmus unabhängig von den dort gespeicherten Objekten zu ermöglichen, wird das von Java bereitgestellte Interface Comparable verwendet, welches folgende Methode ankündigt:

  int compareTo(Object x) 
  // liefert  0, wenn this == x 
  // liefert <0, wenn this  < x
  // liefert >0; wenn this  > x

Alle Objekte einer Klasse, die miteinander verglichen werden sollen, müssen dieses Interface implementieren. Dies ist zum Beispiel bei der Klasse Character der Fall, so dass zwei Characterobjekte a und b über den Aufruf a.compareTo(b) zueinander in Beziehung gesetzt werden können.

Der Suchbaum wiederum implementiert ein Interface Menge, welches die grundsätzlichen Methoden zum Verwalten einer Menge von Objekten ankündigt: lookup, insert und delete.

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 Character verwendeten Klassen und Interfaces:

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.