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 |
Knoten. Die Anzahl der Weg-Knoten ist . | |
Worst case: | Werden die Elemente sortiert eingegeben, so entartet der Baum |
zur Liste, der Aufwand beträgt dann . | |
Average case: | Für zufällige Schlüssel beträgt der Aufwand , |
genauer: Die Wege sind um 39 % länger als im best case. |
Beispiel für einen binären Suchbaum
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 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 a) // liefert 0, wenn this == a // liefert <0, wenn this < a // liefert >0; wenn this > a
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 x und y über den Aufruf x.compareTo(y) 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 Characters verwendeten Klassen und Interfaces:
Multimenge
Zur Verwaltung einer Multimenge (Elemente sind ggf. mehrfach vorhanden) kann ein Suchbaum wie folgt verwendet werden: