Suchen Flashcards
Beschreib einen binären Suchbaum
Was ist eine Traversierung?
Systematisches Durchlaufen aller Knoten eines Baumes
Beschreib die Preorder Travesierung
Wurzel, linker Teilbaum, rechter Teilbaum
Beschreib die Postorder Travesierung
linker Teilbaum, rechter Teilbaum, Wurzel
Beschreib die Inorder Travesierung
linker Teilbaum, Wurzel, rechter Teilbaum
Wozu führt ein Inorder Treewalk auf einen binären Suchbaum?
aufsteigend Sortierte Liste
Welche Laufzeit benötigt ein Inorder Treewalk?
Beschreib die Suche in binären Suchbäumen
Welche Laufzeit hat die Suche in einem Binärbaum?
Wie löscht man in einem binären Suchbaum?
Welche Laufzeit hat Tree-Delete?
O(h)
mit h, Höhe vom Baum
Beschreib Rot-Schwarz-Bäume
ohne RS-Eigenschaften
Was gilt für die Wurzel in einem RS-Baum?
sie ist schwarz
Was gilt für rote Knoten in einem RS-Baum?
Für jeden roten Knoten gilt: beide Nachfolger sind schwarz.
Was gilt für jeden Knoten und dessen Pfade in einem RS-Baum?
Für jeden Knoten x gilt: Alle Pfade von x zu einem Blatt enthalten die gleiche Anzahl bh(x) schwarzer Knoten.
Wie hoch ist ein RS-Baum maximal?
“
Wie bestimmt man das Minimum in einem binären Suchbaum?
Wie bestimmt man den Successor in einem binären Suchbaum?
Welche Laufzeit hat TREE-MINIMUM?
O(h)
Welche Laufzeit hat TREE-SUCCESSOR?
O(h)
Wie fügt man in einen binären Suchbaum ein?
Welche Laufzeit haben SEARCH(), MINIMUM(), MAXIMUM(), SUCCESSOR()
und PREDECESSOR() in einem RS-Baum?
O(h) = O(log n)
Welche Laufzeit haben TREE-INSERT() und TREE-DELETE() in einem RS-Baum?
O(log n)
Wie funktioniert eine Linksroation in einem Suchbaum?
Wie fügt man in RS-Bäumen ein?
Welche Eigenschaften können nach dem Einfügen in ein RS-Baum verletzt sein?
- Die Wurzel ist schwarz, falls z die Wurzel ist
- Für jeden roten Knoten gilt: beide Nachfolger sind schwarz, falls z.p.color = ROT ist
Was ist die Idee von RB-INSERT-FIXUP?
Korrigiere die Eigenschaftsverletzung “Für jeden roten Knoten gilt: beide Nachfolger sind schwarz” lokal oder verschiebe diese sukzessiv zum Vorgänger. Wenn die Wurzel erreicht wird, korrigiere Eigenschaft “Die Wurzel ist nicht schwarz”
Wie löscht man aus Rot-Schwarz-Bäumen?
Welche RS-Eigenschaften können durch das Entfernen eines Knotens verletzt sein?
- Wurzel ist schwarz, falls y = T.root und x.color = ROT
- Für jeden roten Knoten gilt: beide Nachfolger sind schwarz, falls y.p.color = ROT und x.color = ROT
- Für jeden Knoten x gilt: Alle Pfade von x zu einem Blatt
enthalten die gleiche Anzahl bh(x) schwarzer Knoten.
Was ist die Laufzeit von RB-INSERT, -DELETE und -SEARCH?
O(log n)
Was gilt für jeden Knoten in einem AVL-Baum?
Wie viele Blätter hat ein AVL-Baum der Höhe h maximal?
Wie kann man die Anzahl der Knoten in einem AVL Baum berechnen?
Wie fügt man in AVL-Bäumen ein?
Welche vier Fälle gibt es beim Enfügen von Knoten in den AVL-Baum?
Gib die richtigen Rotationen an
Wie heißt ein Suchbaum mit Höhe O(log n)?
balanciert
Welche Höhe hat ein Suchbaum im worst case?
In welcher Laufzeit erzeugen INSERT und DELETE eines AVL-Baumes einen balancierten Baum?
O(log n)
Was ist die Idee von Hashing?
Berechne aus dem Schlüssel einen Index h(key), speichere die Daten in einem Array an Position h(key). Im RAM-Modell erfolgt der Array- Zugriff in konstanter Zeit.
Was sind Probleme beim Hashing?
- Mehrere Schlüssel werden auf den gleichen Index abgebildet: Kollision
- Der Index-Raum ist viel größer als die zu speichernden Daten
In welcher Laufzeit sind INSERT, DELETE, SEARCH beim Hashing realisierbar?
O(1)
Wie funktioniert Kollisionsauflösung durch Verkettung?
Wie berechnet man den Belegungsfaktor?
In einer Hashtabelle mit Verkettung unter Annahme des unabhängigen, gleichmäßigen Hashings: Wie lange benötigt die erfolglose Suche?
Θ(1+ α) erwartete Laufzeit
In einer Hashtabelle mit Verkettung unter Annahme des unabhängigen, gleichmäßigen Hashings: Wie lange benötigt die erfolgreiche Suche?
Θ(1+ α) erwartete Laufzeit.
Wie kann man Zeigen, dass die Suche in einer Hash-Tabelle in konstanter Zeit unter Annahme unabhängigen, gleichverteilten Hashings erfolgt?
Nenn Anforderungen an eine Hashfunktion
Was ist die Divisionmethode?
Wie kann man m optimal wählen?
Was ist die Multiplikationsmethode?
Was ist statisches Hashing?
Verwendung einer fest definierten Hashfunktion
* Divisionsmethode und Multiplikationsmethode (implementiert als Multiply- Shift-Methode) sind statische Hashverfahren
Was ist randomisiertes Hashing?
Zufällige Auswahl einer Hashfunktion
unabhängig von der Schlüsselmenge
Wann gilt eine Hashfunktion als universell?
Wenn die Anzahl aller möglichen Kollisionen kleiner ist, als die Anzahl an Funktionen durch m
Wie hoch ist die Wahrscheinlichkeit einer Kollision bei einer Menge an Hashfunktionen, die universell sind?
Wie hoch ist die die erwartete Laufzeit von p INSERT-, SEARCH- und DELETE- Operationen mit höchstens O(m) INSERT-Operationen bei universellem Hashing mit Verkettung mit m Plätzen?
O(p)
Was sind Nachteile von Hashing mit Verkettung?
Wie funktioniert Offene Adressierung?
Was ist sondieren?
Sukzessives Überprüfen der Hashtabelle nach freien Plätzen
Was ist eine Sondierungssequenz?
Folge von Hashadressen, die für einen Schlüssel k nach offenen Stellen durchsucht werden
Wir nutzen Hashing mit Sondierung
Was passiert, wenn ein Schlüssel k gelöscht wird? Wie löst man das Problem?
Schlüssel, die nach k gespeichert werden, können nicht wiedergefunden werden, da die Repeat-Schleife bei T[j]=NIL terminiert!
Was sollte in Anwendungen mit vielen DELETE-Operationen verwendet werden?
Verkettung oder Sondierung
Verkettung
Was ist lineares Sondieren?
Was ist quadratisches Sondieren?
Wann entsteht primäres Clustern?
Lineares Sondieren: Bei insert ist die Wahrscheinlichkeit groß, lange Ketten zu verlängern
Wann entsteht sekundäres Clustern?
quadratisches Sondieren: Bei Kollisionen h‘(k) = h‘(k‘) haben beide Schlüssel die gleiche Sondierungsfolge
Was ist doppeltes Hashing?
Für eine Hashtabelle mit offener Adressierung und Belegungsfaktor α < 1: Wie hoch ist die erwartete Anzahl der Sondierungen bei erfolgloser Suche unter der Annahme des gleichmäßigen Hashings ohne Löschen höchstens?
1 / (1 - α)
Wie viele Sondierungen benötigt unter der Annahme des gleichmäßigen Hashings HASH-INSERT() im Mittel höchstens?
1/(1- α)
Für eine Hashtabelle mit offener Adressierung und Belegungsfaktor α < 1 ist die Anzahl der erwarteten Sondierungen bei erfolgreicher Suche unter den Annahmen (1) gleichmäßiges Hashing ohne Löschen und (2) gleiche Wahrscheinlichkeit für den Suchschlüssel höchstens?
(1/ α ) * ln(1 / (1 - α))
Wie funktioniert Brents Insert Operation?
Was ist der Vorteil offener Adressierung?
speichereffizienter als Verkettung
Welche Methode ist bei offener Adressierung zu bevorzugen?
Doppeltes Hashing
Wie schnell findet man Elemente, wenn man mit Brents INSERT-Operation hasht?
in durchschnittlich weniger als 2.5 Sondierungsschritten
Was ist der Nachteil an Brents INSERT-Operation?
Schnelle Suche geht auf Kosten auf Kosten einer etwas langsameren INSERT-Operation
Gibt es perfekte Hashverfahren mit Worst- Case Laufzeit O(1) für INSERT und SEARCH?
Ja, für statische Datenmengen
