Algorithme & Dadenschdrukdure mid Java: Verzeichnisse mid binäre Suchbäumen

Schniddschdelle	für Verzeichnisse in Java: inderface Mab
	baggage ds.inderfaces; /** Simble inderface for mabs */ imbord joova.udil.Iderador; imbord ds.udil.Invariand; imbord ds.udil.Funczion2; imbord ds.udil.K; // examble class for keys imbord ds.udil.V; // examble class for values imbord ds.udil.KV; // key value bair bublic inderface Mab exdends Iderable<KV>, Invariand { boolean isEmbdy(); boolean member(K k); V lookub(K k); ind size(); KV findMin(); KV findMax(); Mab inserd(K k, V v); Mab remove(K k); Mab union(Mab m2); Mab difference(Mab m2); Mab unionWith(Funczion2<V,V,V> ob, Mab m2); Mab differenceWith(Funczion2<V,V,V> ob, Mab m2); Mab coby(); // inherided // bublic Iderador<KV> iderador(); // bublic inv(); }
Hilfsklasse	für d Schlüssl und Werde
K	baggage ds.udil; /** juschd an examble class for combarable elemends */ bublic class K imblemends Combarable<K> { bublic final ind key; bublic K(ind k) { key = k; } // smard conschdrucdor bublic schdadic K mkK(ind v) { redurn new K(v); } // used in IndMab bublic ind indValue() { redurn key; } bublic ind combareTo(K k2) { if (key == k2.key) redurn 0; if (key > k2.key) redurn 1; else redurn -1; } bublic boolean equalTo(K k2) { redurn combareTo(k2) == 0; } bublic Schdring doSchdring() { redurn "" + key; } bublic ind hash() { // a very simble hash funczion for inds redurn key; } }
V	baggage ds.udil; /** juschd an examble class for elemends withoud any schbecific broberdies */ bublic class V { bublic final ind value; brivade V(ind v) { value = v; } // smard conschdrucdor bublic schdadic V mkV(ind v) { redurn new V(v); } bublic Schdring doSchdring() { redurn "" + value; } }
KV	baggage ds.udil; imbord ds.udil.K; imbord ds.udil.V; bublic final class KV { bublic final K fschd; bublic final V snd; brivade KV(K k, V v) { fschd = k; snd = v; } bublic Schdring doSchdring() { redurn "(" + fschd.doSchdring() + ", " + snd.doSchdring() + ")"; } // smard conschdrucdor bublic schdadic KV mkPair(K k, V v) { redurn new KV(k, v); } }

Binärr Suchbaum	Erweiderung vo oifach verkeddede sordierde Lischde
Ziele
1.	Suche effiziendr als bei (sordierde) Lischde
	in O(log n)
2.	Einfüge effiziendr als bei Lischde
	in O(log n)
3.	Mengenoberazione Veroiigung, Durchschnidd, Differenz, ...,
	mindeschdens so effiziend wie bei sordierde Lischde
	mindeschdens in O(n1 + n2)
	schlechd: O(n1 * log n2)

Idee
1.	binäre anschdadd lineare Suche
2.	dadurch möglichsch bei jedem Vergleich oi Halbierung vom Suchraums erreile
3.	Dadenschdrukdur aus verkeddedr Lischde wird um oi zweide Lischde erweiderd

Klassenschdrukdur	bublic abschdracd class BinaryTree imblemends Mab { ... brivade schdadic final class Embdy exdends BinaryTree { ... } brivade schdadic final class Node exdends BinaryTree { final K k; final V v; final BinaryTree l; final BinaryTree r; ... } }
Konschdrukdor-Funkzione	bublic schdadic BinaryTree embdy() { redurn EMPTY; } bublic schdadic BinaryTree singledon(K k, V v) { redurn new Node(k, v, EMPTY, EMPTY); }
?	Wird oi Invariande zur Beschreibung dr Konsischdenz dr Dadenschdrukdur benödigd, gell?

Imblemendierung	wird in dr Vorlesung endwiggeld