Mengenimplementierung Flashcards
effiziente Suchverfahren
° Es sollen nicht alle Elemente mit dem zu suchenden Element verglichen werden müssem (linearer Aufwand)
° Anforderung an Elemente, sie sollen: sortierbar oder kategorisierbar sein
° Sortierbare Elemente ermöglichen eine binäre Suche oder eine Realisierung mit einem Suchbaum
° Kategorisierbare Elemente ermöglichen Hash-Verfahren
Bäume
° Knoten durch Kanten miteinander verbunden
° Kinder
° Knoten immer max einen Vorgängerknoten
° Knoten ohne Vorgänger heißt Wurzel des Baumes
° Knoten ohne Kinder = Blatt
° Bäum sind rekursiv
° Breiten- oder Tiefensuche
Binäre Suchbäume
° Ein Knoten hat maximal zwei Kinder
° Jeder Knoten enthält ein sortierbares Element
° Im linken Unterbaum sind alle kleineren Elemente
° Im rechten Unterbaum sind alle größeren Elemente
° Merkmale:
- voller binärer Baum mit Höhe h hat 2^h Blätter
- Zahl der Knoten 2^(h+1)-1
Balancierte binäre Suchbäume
° für jeden Knoten gilt, dass die Höhe seiner beiden Unterbäumesich max um eins unterscheiden
° Höhe h berechnet sich dann logarithmisch aus der Anzahl n der Knoten im Baum: h = Id(n) (Id ist Logarithmus Dualis, zur Basis 2)
° Die Suche muss von der Wurzel bis zu jedem Blatt höchstens Id(n) Vergleiche vornehmen; der Aufwand ist in einer Größenordnung O(log(n))
° Baum-Implementationen des JCF (TreeSet und TreeMap) benutzen binäre, balancierte Bäume (die Elemente müssen sortierbar sein)
Hash-Verfahren
° Grundidee, elemente auf Indexstruktur abzubilden
° Aus Elementen ist unmittelbar ein Index berechenbar
° Man hat mehrere Listen und das Wissen in welcher gesucht werden muss
- Jede Liste enthält die Elemente einer Kategorie
- Jedes Element kann Auskunft geben, zu welcher Kategorie es gehört
Hash-Tabelle
° Für das zu suchende Element wird zuerst der Index der Liste in der Tabelle ermittelt, in der Elemente der gleichen Kategorie liegen
° Nach dem (schnellen) indexbasierten Zugriff auf die Liste wird diese dann (linear) durchsucht
° Im Indealfall enthalten die Listen max ein Element
° Nach der Indexberechnung ist dann für eine Suche max ein Vergleich notwendig
° Sind mehr als ein Element enthalten, werden die überschüssigen Elemente als Überläufe bezeichnet
- Die Listen werden auch als Überlaufbehälter bezeichnet
Hash-Funktion
° bildet ein Element auf einen ganzzahligen Wert ab (int)
° Der berechnete Wert bildet eine Kategorie: Alle Elemente mit demselben Wert fallen in dieselbe Kategorie
- Wen Zwei verschiedene Elemente auf denselben Wert abbilden, wird dies als Kollision bezeichnet
- Der berechnete Wert muss in einem zweiten Schritt auf einen Index in der Hash-Tabelle abgebildet werden
° Entscheidend ist die Güte der Hash-Funktion: Je gleichmächtiger sie die Elemente in der Tabelle verteilt, desto schneller ist das Verfahren
° Eine ideale Hash-Funktion bildet alle Schlüssel eins-zu-eins auf unterschiedliche Integerwerte ab, die fortlaufend sind und bei Null beginnen
