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 = 2h - 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

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

Interfaces

Interfaces enthalten nur Methodenköpfe und Konstanten. Alle in einem Interface definierten Methoden sind implizit abstract. Ein Interface stellt eine Schnittstelle dar und legt damit die Funktionalität ihrer Methoden fest, ohne diese zu implementieren. Dies geschieht im Gegensatz zu einer abstrakten Klasse nicht in einer Subklasse, sondern in einer beliebigen Klasse, die dies zuerst in einer implements-Klausel deklariert und die dann eine Implementation aller Methoden des Interface bereitstellen muss. Verwendet werden kann ein Interface auch ohne Kenntnis der konkreten Implementation. Source: Comparable.java     JavaDoc: Comparable.html     Source: CharComparable.java     JavaDoc: CharComparable.html     Source: StringComparable.java     JavaDoc: StringComparable.html    

Source: SuchBaum.java     JavaDoc: SuchBaum.html    

Source: SuchBaumTest.java     JavaDoc: SuchBaumTest.html     Applet: Speichern von Mehrfachexemplaren in einem Suchbaum

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.