Algorithmen & Datenstrukturen mit Java: Verzeichnisse mit binären Suchbäumen

Schnittstelle	für Verzeichnisse in Java: interface Map
	package ds.interfaces; /** Simple interface for maps */ import java.util.Iterator; import ds.util.Invariant; import ds.util.Function2; import ds.util.K; // example class for keys import ds.util.V; // example class for values import ds.util.KV; // key value pair public interface Map extends Iterable<KV>, Invariant { boolean isEmpty(); boolean member(K k); V lookup(K k); int size(); KV findMin(); KV findMax(); Map insert(K k, V v); Map remove(K k); Map union(Map m2); Map difference(Map m2); Map unionWith(Function2<V,V,V> op, Map m2); Map differenceWith(Function2<V,V,V> op, Map m2); Map copy(); // inherited // public Iterator<KV> iterator(); // public inv(); }
Hilfsklassen	für die Schlüssel und Werte
K	package ds.util; /** just an example class for comparable elements */ public class K implements Comparable<K> { public final int key; public K(int k) { key = k; } // smart constructor public static K mkK(int v) { return new K(v); } // used in IntMap public int intValue() { return key; } public int compareTo(K k2) { if (key == k2.key) return 0; if (key > k2.key) return 1; else return -1; } public boolean equalTo(K k2) { return compareTo(k2) == 0; } public String toString() { return "" + key; } public int hash() { // a very simple hash function for ints return key; } }
V	package ds.util; /** just an example class for elements without any specific properties */ public class V { public final int value; private V(int v) { value = v; } // smart constructor public static V mkV(int v) { return new V(v); } public String toString() { return "" + value; } }
KV	package ds.util; import ds.util.K; import ds.util.V; public final class KV { public final K fst; public final V snd; private KV(K k, V v) { fst = k; snd = v; } public String toString() { return "(" + fst.toString() + ", " + snd.toString() + ")"; } // smart constructor public static KV mkPair(K k, V v) { return new KV(k, v); } }

Binärer Suchbaum	Erweiterung von einfach verketteten sortierten Listen
Ziele
1.	Suche effizienter als bei (sortierten) Listen
	in O(log n)
2.	Einfügen effizienter als bei Listen
	in O(log n)
3.	Mengenoperationen Vereinigung, Durchschnitt, Differenz, ...,
	mindestens so effizient wie bei sortierten Listen
	mindestens in O(n1 + n2)
	schlecht: O(n1 * log n2)

Idee
1.	binäre anstatt lineare Suche
2.	dadurch möglichst bei jedem Vergleich eine Halbierung des Suchraums erreichen
3.	Datenstruktur aus verketteter Liste wird um eine zweite Liste erweitert

Klassenstruktur	public abstract class BinaryTree implements Map { ... private static final class Empty extends BinaryTree { ... } private static final class Node extends BinaryTree { final K k; final V v; final BinaryTree l; final BinaryTree r; ... } }
Konstruktor-Funktionen	public static BinaryTree empty() { return EMPTY; } public static BinaryTree singleton(K k, V v) { return new Node(k, v, EMPTY, EMPTY); }
?	Wird eine Invariante zur Beschreibung der Konsistenz der Datenstruktur benötigt?

Implementierung	wird in der Vorlesung entwickelt