SearchTree

Suchbäume

Die Klasse SearchTree implementiert eine Map, die Schlüssel (keys) auf Werte (values) abbildet. Implementieren Sie die zwei folgenden Methoden:

• insert(Comparable key, T value): Einfügen eines Schlüssel-Wert-Paares. Implementieren Sie das Einfügen nicht iterativ (wie in der Vorlesung), sondern rekursiv.
• countSmaller(Comparable key): Gibt die Anzahl der Elemente im Baum zurück, die kleiner sind als der übergebene Schlüssel. Implementieren Sie die Methode möglichst effizient, d.h. es sollen nicht immer pauschal alle Knoten im Baum besucht werden.