Transcript
Aufgabe (Hashing) Gegeben sei eine Hashtabelle mit 10 Feldern fu ¨r Eintr¨age (Index 0 bis 9) und eine Hashfunktion h(k) = k mod 10. Fu ¨hren Sie fu ¨r die folgenden Hashverfahren einen Schreibtischtest durch, indem Sie jeweils die Werte 56, 34, 6, 13, 94, 27, 47 in dieser Reihenfolge in eine leere Tabelle einfu ¨gen und diese nach jeder Einfu ¨geoperation ausgeben. 1
Hashing mit direkter Listenverkettung Hierbei ist die Hashtabelle als Array von einfach verketteten Listen realisiert.
2
Offenes Hashing mit linearem Sondieren Bei Kollisionen wird hier das einzufu ¨gende Element an der n¨achsten freien Stelle links vom berechneten Hashwert eingefu ¨gt. Das heißt, die Sondierungsreihenfolge (die Reihenfolge, in der die Pl¨atze im Array durchgegangen werden, bis erstmals ein freier Platz angetroffen wird) ist gegeben durch s(k, i) = (h(k) − i) mod 10 fu ¨r i = 0, . . . , 9.
Aufgabe (Hashing) Gegeben sei eine Hashtabelle mit 10 Feldern fu ¨r Eintr¨age (Index 0 bis 9) und eine Hashfunktion h(k) = k mod 10. Fu ¨hren Sie fu ¨r die folgenden Hashverfahren einen Schreibtischtest durch, indem Sie jeweils die Werte 56, 34, 6, 13, 94, 27, 47 in dieser Reihenfolge in eine leere Tabelle einfu ¨gen und diese nach jeder Einfu ¨geoperation ausgeben. 3
Doppeltes Hashing Das doppelte Hashing ist ein offenes Hashing, bei dem die Sondierungsreihenfolge von einer zweiten Hashfunktion h0 (k) = 1 + (k mod 8) abh¨angt. Die Position fu ¨r das i-te Sondieren ist bestimmt durch s(k, i) = (h(k) − i · h0 (k)) mod 10 fu ¨r i = 0, . . . , 9.
4
Uniformes offenes Hashing Hier erh¨alt jeder Schlu ¨ssel mit gleicher Wahrscheinlichkeit eine der 10! Permutationen von {0, 1, . . . , 9} als Sondierungsreihenfolge. Als zuf¨allige“ Permutationen nutzen Sie: ” L(56) = 2, 9, 3, 0, 8, 7, 6, 1, 4, 5 L(94) = 6, 8, 4, 0, 9, 1, 5, 2, 3, 7 L(34) = 1, 5, 9, 3, 7, 4, 8, 6, 2, 0
L(27) = 4, 2, 7, 5, 1, 8, 9, 0, 3, 6
L(6) = 9, 8, 5, 2, 1, 7, 0, 6, 3, 4
L(47) = 1, 9, 6, 0, 3, 5, 2, 8, 7, 4
L(13) = 1, 4, 5, 2, 0, 7, 3, 6, 9, 8
Bin¨are Suchb¨aume (Definition)
Bin¨arer Suchbaum: (Geordneter gewurzelter) bin¨arer Baum, der das Search Constraint erfu ¨llt.
Search Constraint: Fu ¨r alle Knoten v gilt alle Schlu ¨ssel im linken Teilbaum von v sind kleiner (oder gleich) dem Schlu ¨ssel von v, alle Schlu ¨ssel des rechten Teilbaum von v sind gr¨oßer (oder gleich) dem Schlu ¨ssel von v.
Bin¨are Suchb¨aume (Einfu¨gen/Entfernen) Fu ¨hren sie die folgenden Operationen in der gegebenen Reihenfolge aus. Geben sie nach jeder Operation den neuen Baum an. 1
insert(16), insert(11) 10 5
14
3
2
8
15
delete(24), delete(10) 20 10 2
24 18
15 12 14
30 19
25
40
Traversierungen von B¨aumen Pre-Order-Traversierung (w, L, R) 1
Besuche Wurzel w
2
Pre-Order-Traversierung auf linkem Teilbaum von Wurzel w
3
Pre-Order-Traversierung auf rechtem Teilbaum von Wurzel w
In-Order-Traversierung (L, w, R) 1
In-Order-Traversierung auf linkem Teilbaum von Wurzel w
2
Besuche Wurzel w
3
In-Order-Traversierung auf rechtem Teilbaum von Wurzel w
Post-Order-Traversierung (L, R, w) 1
Post-Order-Traversierung auf linkem Teilbaum von Wurzel w
2
Post-Order-Traversierung auf rechtem Teilbaum von Wurzel w
3
Besuche Wurzel w
Traversierungen von B¨aumen (Aufgabe)
1
Welche der drei Traversierungen ist geeignet um die Schlu ¨ssel eines Suchbaumes in sortierter Reihenfolge auszugeben?
2
Ein Suchbaum enthalte die Schlu ¨ssel 1, 3, 4, 7, 9, 13, 20, 22. In der Pre-Order-Traversierung (w, L, R) werden die Schlu ¨ssel in der folgenden Reihenfolge besucht: 4, 1, 3, 20, 9, 7, 13, 22. Geben Sie den Suchbaum an.
AVL-B¨aume (Definition)
AVL-Baum: Bin¨arer Suchbaum mit Height Constraint
Height Constraint: Fu ohe des linken und des rechten ¨r alle Knoten v unterscheiden sich die H¨ Teilbaums um maximal 1.
AVL-B¨aume (Einfu¨gen)
Einfu¨gen eines Schlu¨ssels: 1 2
Knoten einfu ¨gen (wie bei Suchb¨aumen) Balancen berechnen: Beginnend bei eingefu ¨gtem Knoten bis zur ersten Disbalance (+2 oder -2) auf dem Pfad bis zu der Wurzel.
3
ggf. Rotation oder Doppelrotation um diese Disbalance auszugleichen
4
fertig (maximal eine Rotation oder Doppelrotation n¨otig)
AVL-B¨aume (Entfernen)
Entfernen eines Schlu¨ssels: 1
Knoten entfernen (wie bei Suchb¨aumen)
2
Balancen berechnen: Beginnend bei entferntem Knoten (das ist ggf. der symmetrische Vorg¨anger/Nachfolger) bis zur ersten Disbalance (+2 oder -2) auf dem Pfad bis zu der Wurzel.
3
ggf. Rotation oder Doppelrotation um diese Disbalance auszugleichen
4
Wiederhole 2. und 3. (ab dem Knoten, wo vorher die Disbalance war), solange bis Wurzel erreicht wurde. (Es k¨onnen mehrere Rotatationen oder Doppelrotationen n¨otig sein.)
