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.
package de.hsrm.ads;
public class SearchTree< C extends Comparable<C>, T> {
Node root;
class Node {
Node left;
Node right;
C key;
T value;
Node(C key, T value) {
this.left = null;
this.right = null;
this.value = value;
this.key = key;
}
}
public SearchTree() {
root = null;
}
public void insert(C key, T value) {
// FIXME
}
public int countSmaller(C key) {
// FIXME
}
public static void main(String[] args) {
}
}
Subato
