Datenstrukturen - uni-frankfurt.de · 2012. 7. 3. · Der Zick-Zack Fall w v u A B C Tiefe d Fallannahme:Ein neues Blatt wurde im Teilbaum mit Wurzel u eingef ugt undTiefe(B) >Tiefe(C)

Datenstrukturen

Mariano Zelke

Sommersemester 2012

Der Zick-Zack Fall

w

v

u

A

B C

Tiefe d

Fallannahme: Ein neues Blatt wurde im Teilbaum mit Wurzel u eingefugtund Tiefe(B) > Tiefe(C ).

I Die Reparatur muss nur dann fortgesetzt werden, wenn die Tiefedes Teilbaums von u um 1 angestiegen ist.

I Sei d die neue Tiefe des Teilbaums von u. Wie im Zick-Zick Fall istnur der Fall Tiefe(A) = d − 2 kritisch.

Mariano Zelke Datenstrukturen 2/24

Tiefe(A) = d − 2

w

v

u

A

B C

d−2

d−1 d−2

w

v

u

A B

C

d−2 d−1

d−2

b(u)=2

I Da d − 1 =Tiefe(B) > Tiefe(C ) = d − 2, folgt

Tiefe(A) = Tiefe(C ) = d − 2 und Tiefe(B) = d − 1.

I Eine Linksrotation in v ist keine Reparatur.B wandert vom rechten zum linken Teilbaum und dieAVL-Eigenschaft bleibt verletzt, da Tiefe (A) = Tiefe(C ).


Tiefe(A) = d − 2

wv

u

bA

C

B1 B2

d−2

d−2oderd−3

d−2 oderd−3

d−2

Zuerst eineRechtsrotation in u

wv

u

b

A

B1

B2 C

Danach eineLinksrotation in v

wb

v u

A B1 B2 Cd − 2d−2oderd−3

d − 2


Nach der Doppelrotation

wb

v u

A B1 B2 Cd − 2d−2oderd−3

d − 2

I Die Tiefe ist um 1 gesunken, denn Tiefe (A) = Tiefe(C ) = d − 2und d − 3 ≤ Tiefe(B1), Tiefe(B2) ≤ d − 2.

I Die Tiefe des Knotens b stimmt jetzt mit der Tiefe von v vor demEinfugen des neuen Blatts uberein.

I Nach Setzen der neuen Balance-Grade kann die Reparaturabgebrochen werden.


Der Zack-Zick Fall

w

u

v

A B

C

Fallannahme: Ein neues Blatt wurde im Teilbaum mit Wurzel u eingefugtund Tiefe(B) > Tiefe(A).

Der Zack-Zick Fall wird analog zum Zick-Zack Fall behandelt.


Beispiel6

3 8

2 4 7 9

1 5 11

10

Abschließend wird nun nochder Schlussel 10 eingefugt.

Damit ist die Balance

bei 9 verletzt. b=−2

Es ist der Zick-Zack-Fall entstanden. Dies lost eine Doppelrotation aus:

6

3 8

2 4 7 9

1 5 10

11

Zuerst eine Rechts-

rotation in 11...6

3 8

2 4 7 10

1 5 9 11

...dann eine Links-

rotation in 9.


Zusammenfassung

Die Operationen lookup und insert haben die worst-case LaufzeitO(log2 n) fur AVL-Baume mit n Knoten.

I Auch mit AVL-Baumen konnen wir sortieren:I Fuge n Schlussel in Zeit O(n · log2 n) einI gib anschließend die Schlussel in Inorder aus.

Eine Animation zu AVL-Baumen findet sich hier.


http://www.qmatica.com/DataStructures/Trees/AVL/AVLTree.html

Das Worterbuch – Hashing


Die Bitvektor-Datenstruktur

Das Worterbuchproblem wird einfacher, wenn die Menge U dermoglicherweise einzufugenden Daten in den Hauptspeicher passt.

I Benutze die Bitvektor-Datenstruktur:

In einem booleschen Array wird fur jedes Element u ∈ U in der Zellef (u) vermerkt, ob u prasent ist.

Bis auf die Berechnung von f (u) gelingt damit die Ausfuhrung einerlookup-, insert- oder remove-Operation in konstanter Zeit!

I Selbst bei einem kleinen Universum U ist aber die Wahl einergeeigneten Funktion f moglicherweise schwierig.

I Zudem ist in praktischen Anwendungen im Allgemeinen dasUniversum der moglichen Schlussel zu groß:

Wenn Nachnamen als Schlussel verwandt werden, und selbst wennnur Nachnamen der Lange hochstens 10 auftreten, gibt es2610 ≥ 210 · 1010 ≥ 103 · 1010 = 1013, also mehr als 10 Billionenmogliche Schlussel!


Hashing – Anwendungen

I eine Hashfunktion bildet Elemente aus einem großen Universum ineine kleine Zielmenge ab (die Ausgabe heißt auch Hashcode)

I Idee: Große Datenmengen platzsparend verwalten, Eintrage schnellauffinden

I Anwendungen:I Hash-Tabellen zum schnellen Suchen in großen DatenmengenI Kryptographie, etwa fur Digitale Signaturen (siehe auch

Schnorr-Signatur, Link)I Implementierung des abstrakten Datentyps Worterbuch


http://de.wikipedia.org/wiki/Schnorr-Signatur

Hashing

Hashing versucht die Schnelligkeit und die Einfacheit derBitvektor-Datenstruktur auch im allgemeinen Fall zu bewahren.

I Sei U die Menge aller moglichen Schlussel und sei m die Große einerim Hauptspeicher abspeicherbaren Tabelle.

I Eine Funktionh : U → {0, 1, ...,m − 1}

heißt eine Hashfunktion.I Zum Beispiel konnen wir insert (x, info) implementieren,

indem wirI h(x) = i berechnen undI (x , info) in Zelle i der Tabelle eintragen.

Aber was passiert bei einer Kollision, wenn also Zelle i bereitsbesetzt ist?

Wir beschreiben zwei Hashing-Verfahren, Hashing mit Verkettung undHashing mit offener Adressierung.


Hashing mit Verkettung

Fur jede Zelle i wird eine anfanglich leere Liste angelegt.

I Jede Liste wird sortiert gehalten.

I Fur lookup(x): Durchlaufe die Liste von h(x).

I Fur insert(x) und remove(x): Fuhre die insert- undremove-Operation fur einfach-verkettete Listen aus.


Beispiel Hashing mit VerkettungWir benutzen eine Hashtabelle der Große 7 und die Hashfunktion f (x) = x mod 7.

insert(14): f (14) = 0

insert(63): f (63) = 0

insert(9): f (9) = 2

insert(42): f (42) = 0

insert(31): f (31) = 3

0 1 2 3 4 5 6

14

42

63

9 31

lookup(9) (erfolgreich) und

lookup(8) (nicht erfolgreich)

benotigen je einen Suchschritt,

lookup(63) (erfolgreich)

benotigt drei.


benotigt nur einen, da bei

gefundener 14 die Suche

wegen Sortierung der Listen

abgebrochen werden kann.


Die Wahl der Hashfunktion

Jeder Schlussel x wird als Bitvektor dargestellt. Wir konnen alsoannehmen, dass x eine naturliche Zahl ist.

I Eine beliebte und gute Wahl ist h(x) = x mod m.h(x) kann schnell berechnet werden und wird bei

”guter“ Wahl von

m zufriedenstellende Ergebnisse liefern.I Was ist eine schlechte Wahl von m?

I Angenommen, m ist eine Zweierpotenz.I Wenn die Schlussel Character-Strings sind, dann werden alle

Character-Strings mit gleicher Endung auf dieselbe Zelle gehasht.I Haufig auftretende Endungen provozieren viele Kollisionen und damit

lange Listen: Die Bearbeitungszeit der einzelnen Operationen wachst!

Wahle stattdessen Primzahlen mit großem Abstand zurnachstliegenden Zweierpotenz.


Wie schnell ist Hashing mit Verkettung?

Annahme: es befinden sich n Schlussel in einer Tabelle mit m Zellen.Wir sagen dann, dass λ = n

m der Auslastungsfaktor der Tabelle ist.

Wie schnell wird eine insert(x), remove(x) oder lookup(x)Operation ausgefuhrt?

I Bestenfalls ist die Liste fur h(x) = i leer und wir erreichen einekonstante Laufzeit.

I Schlimmstenfalls sind alle n Schlussel auf die Liste von i verteilt unddie worst-case Laufzeit Θ(n) folgt.

Weder best-case noch worst-case Laufzeit scheinen verlasslicheVoraussagen der tatsachlichen Laufzeit zu sein.Wir sollten die erwartete Laufzeit betrachten.


Laufzeiten

I Die erwartete Lange einer Liste fur Hashing mit Verkettung isthochstens 1 + λ.

I Die erwartete Laufzeit einer insert-, remove- oder lookup-Operationist hochstens O(1) +O(λ):

Die Hashfunktion ist auszuwerten unddann muss die Hashliste durchlaufen werden.

I Hashing mit Verkettung ist ein hochgradig praxistauglichesVerfahren.

I Einziger Nachteil:Durch die Verwendung von Listen, und damit durch die Verwendungvon Zeigern, entsteht zusatzlicher Speicherbedarf.


Hashing mit offener Adressierung

Wir arbeiten mit einer Folge

h0, ..., hm−1 : U → {0, ...,m − 1}

von Hashfunktionen. Setze i = 0.

(1) Wenn die Zelle hi (x) frei ist, dann fuge x in Zelle hi (x) ein.

(2) Ansonsten setze i = i + 1 und gehe zu Schritt (1).

Die Anzahl der Fehlversuche”sollte“ ansteigen, wenn λ zu groß

wird. Was ist in einem solchen Fall zu tun?

I Wenn der Auslastungsfaktor großer als 1/2 wird, dann lade dieTabelle in eine doppelt so große Tabelle.

I Die Zeit fur die Reorganisation wird durch die schnellere Bearbeitungder Operationen amortisiert.

Wie sollen die einzelnen Operationen implementiert werden?


Implementierung von Lookup, Insert und Remove

I lookup und insert lassen sich fur jede Folge von Hashfunktionenleicht implementieren.

I Kopfzerbrechen bereitet remove: Wird nach Einfugen des Schlusselsx in Zelle h1(x) der Schlussel in Zelle h0(x) entfernt, dann hat dieOperation lookup (x) ein Problem:

I Ist x nicht prasent, weil Zelle h0(x) leer ist oderI muss weiter gesucht werden?I Bringe eine

”entfernt“ Markierung nach Loschen des Schlussels in

Zelle h0(x) an. Die erwartete Laufzeit einer erfolglosen Suche wirdaber anwachsen.

Hashing mit offener Adressierung sollte vermieden werden, wenn vieleDaten entfernt werden.


Lineares Austesten

In der Methode des linearen Austestens wird die Folge

hi (x) = (x + i) mod m

benutzt: Also wird die jeweils nachste Zelle untersucht.

Fur jeden Schlussel x ist die Folge h0(x), . . . , hm−1(x) eine zyklischeVerschiebung der Zellen. Insbesondere wird jede Zelle

”getestet“.

Lineares Austesten fuhrt zur Klumpenbildung.I Angenommen, die Daten besetzen ein Intervall {i , i + 1, . . . , j − 1, j}

von Zellen.I Wenn ein weiterer Schlussel x mit h0(x) ∈ {i ,+1, . . . , j − 1, j}

eingefugt wird, dann wird x am Ende des Intervalls eingefugt.I Das Intervall wachst und dementsprechend steigt der Aufwand fur die

einzelnen Operationen.


Beispiel Lineares AustestenWir benutzen eine Hashtabelle der Große 7 und die Funktion f (x) = x mod 7.

Die Folge von Hashfunktionen ist hi (x) = (f (x) + i) mod 7 fur i = 0, 1, . . .

insert(14): h0(14) = 0

14

insert(63): h0(63) = 0

h1(63) = 1

63

insert(9): h0(9) = 2

9

insert(42): h0(42) = 0

h1(42) = 1

h2(42) = 2

h3(42) = 3

42

insert(31): h0(31) = 3

h1(31) = 4

31

0 1 2 3 4 5 6lookup(9) (erfolgreich) und


benotigen je einen Suchschritt. lookup(42) (erfolgreich) benotigt vier und

lookup(7) (nicht erfolgreich) sechs Suchschritte.


Doppeltes Hashing

Wir benutzen zwei Hashfunktionen f und g und verwenden die Folge

hi (x) = (f (x) + i · g(x)) mod m.

I Die Klumpenbildung wird vermieden.

I Man erhalt gute Ergebnisse bereits fur

f (x) = x mod m und g(x) = m∗ − (x mod m∗).

I Wahle m als Primzahl und fordere m∗ < m.I g(x) ist stets von Null verschieden.I Wenn f (x) + i · g(x) = f (x) + j · g(x) mod m,

dann (i − j) · g(x) = 0 mod m. Also folgt i = j .I Damit gilt {hi (x) | 0 ≤ i < m} = {0, . . . ,m − 1}, das heißt:

Im doppelten Hashing werden alle Zellen getestet.


Beispiel Doppeltes HashingWir benutzen eine Hashtabelle der Große 7 und die Funktionen f (x) = x mod 7

und g(x) = 5 − (x mod 5). Die Folge von Hashfunktionen ist

hi (x) = (f (x) + i ·g(x)) mod 7 fur i = 0, 1, . . .insert(14): h0(14) = 0

14

insert(63): h0(63) = 0

h1(63) = 2

63

insert(9): h0(9) = 2

h1(9) = 3

9

insert(42): h0(42) = 0

h1(42) = 3

h2(42) = 6

42

insert(31): h0(31) = 3

h1(31) = 0

h2(31) = 4

31

0 1 2 3 4 5 6lookup(14) (erfolgreich) und


benotigen je einen Suchschritt. lookup(42) (erfolgreich) benotigt drei und

lookup(7) (nicht erfolgreich) funf Suchschritte.Mariano Zelke Datenstrukturen 23/24

Zusammenfassung (Link)

Der Auslastungsfaktor sei λ.

I Hashing mit Verkettung besitzt fur alle Operationen eine erwarteteLaufzeit von hochstens O(1) + λ.

I Wegen der Klumpenbildung des linearen Austestens werden dieOperationen bei hoher Auslastung im Durchschnitt 1

2 · (1 + 1(1−λ)2

)

Zellen getestet. Allerdings ist lineares Austesten”cache-freundlich“.

I Die erwartete Laufzeit einer erfolglosen Suche fur doppeltes Hashingist hochstens 1

1−λ .

Der Auslastungsfaktor fur das lineare Austesten oder das doppelteHashing sollte nicht zu groß werden: Lade in eine doppelt so großeTabelle, wenn λ > 1/2.

Eine Animation zum Hashing findet sich hier.


http://de.wikipedia.org/wiki/Hashtabelle

http://www.engin.umd.umich.edu/CIS/course.des/cis350/hashing/WEB/HashApplet.htm

Documents

Datenstrukturen - uni-frankfurt.de · 2012. 7. 3. · Der Zick-Zack Fall w v u A B C Tiefe d Fallannahme:Ein neues Blatt wurde im Teilbaum mit Wurzel u eingef ugt undTiefe(B) >Tiefe(C)