Transcript
¨ Wien Technische Universitat Institut fur ¨ Computergraphik und Algorithmen Arbeitsbereich fur ¨ Algorithmen und Datenstrukturen
184.253 Algorithmen und Datenstrukturen 1 VL 4.0
¨ Ubungsblatt 3 ¨ f¨ur die Ubung am Montag 11. bzw. Dienstag 12. Dezemberr 2006
Aufgabe 3.1 Bestimmen Sie eine Folge von 12 Zahlen, die – wenn sie in genau der vorgegebenen Reihenfolge eingef¨ugt werden – zu einem bin¨arer Suchbaum f¨uhren, der folgende Eigenschaften besitzt: • Der Baum hat Tiefe 9. • Jeder Knoten, der ein rechter Sohn seines Vaters ist, besitzt kein linkes Kind. • Jeder Knoten, der ein linker Sohn seines Vaters ist, besitzt kein rechtes Kind.
Aufgabe 3.2 L¨oschen Sie aus dem abgebildeten bin¨aren Suchbaum in der angegebenen Reihenfolge die Knoten 20, 16 und 5. Zeichnen Sie den Baum nach jeder L¨oschung eines Knotens. 15
5
3
16
12
10
20
13
6
18
17
7
8
23
22
2 Aufgabe 3.3 Bei einer In-Order-Traversierung eines gegebenen bin¨aren Baumes ergibt sich folgende Knotenliste: 0, 1, 3, 5, 6, 7, 8, 10, 11, 13, 17, 18. Bei einer Pre-Order-Traversierung des gleichen Baumes ergibt sich: 8, 5, 1, 0, 3, 7, 6, 11, 10, 17, 13, 18. Zeichnen Sie den zugrundeliegenden Baum und tragen Sie die entsprechenden Knotenwerte ein.
Aufgabe 3.4 In der Vorlesung (im Skriptum) haben Sie die nicht-rekursive Variante der Bin¨aren Suche kennengelernt. Entwickeln Sie nun den Pseudocode f¨ur eine rekursive Variante. Visualisieren Sie Ihren Algorithmus anhand der folgenden Beispielfolge: A, C, F, G, H, I, K, M, N, P, Q, S, T, V, W, X, Z Geben Sie jeden rekursiven Aufruf Ihres Algorithmus mit den aktuellen Grenzen (links, rechts) an und markieren Sie die Grenzen und das jeweilige mittlere Element in der folgenden Tabelle. Gesucht wird der Schl¨ussel V . Aufruf (Grenzen)
A
C
F
G
H
I
K
M
N
P
Q
S
T
Hinweis: Die richtige L¨osung ben¨otigt nicht unbedingt alle Zeilen der Tabelle.
V
W
X
Z
3 Aufgabe 3.5 Ab wie vielen Suchanfragen lohnt sich eine Bin¨are Suche (inklusive der daf¨ur notwendigen Sortierung) im Vergleich zu einer sequentiellen Suche in einem Feld der L¨ange n? Gehen Sie vom Worst-Case aus! Geben Sie f¨ur n = 8 die Anzahl der Suchanfragen an, ab der die Bin¨are Suche effizienter arbeitet!
Aufgabe 3.6 Gegeben ist ein bin¨arer Suchbaum T , in dem Fließkomma-Zahlen abgespeichert sind. Sei B die Menge der Zahlen, die in dem Baum abgelegt sind. Gehen Sie davon aus, dass alle Zahlen im Baum paarweise verschieden sind. Schreiben Sie ein Programm in Pseudocode, welches ein Paar (a, b) von Schl¨usseln in B findet, bei dem |a−b| minimal unter allen Paaren von Schl¨usseln in B ist. Ihr Programm soll den Baum nur ein Mal durchlaufen und keine Listen oder Arrays verwenden. Sie d¨urfen Funktionen wie Maximum, Minimum, Predecessor und Successor, die in er Vorlesung behandelt wurden, als Black Box benutzen, ohne ihren Code anzugeben.
Aufgabe 3.7 Gegeben sei folgender AVL-Baum direkt nach dem Einf¨ugen eines neuen Elements:
10 8 6 2
16 14
22 18
Ist die AVL-Eigenschaft in diesem Baum verletzt? Falls ja, f¨uhren Sie die notwendigen Maßnahmen durch, um die AVL-Bedingung wieder herzustellen, und zeichnen Sie den Baum in seinem korrigierten Zustand. F¨uhren Sie danach folgende Operationen in diesem AVL-Baum in der angegebenen Reihenfolge durch und zeichnen Sie den Baum nach jeder Operation. Achten Sie darauf, dass die AVL-Eigenschaft immer erhalten bleibt.
4 a) F¨ugen Sie 19 in den AVL-Baum ein. b) F¨ugen Sie 7 in den AVL-Baum ein. c) L¨oschen Sie 22 aus dem AVL-Baum. d) F¨ugen Sie 13 in den AVL-Baum ein.
Aufgabe 3.8 Gegeben sei ein AVL-Baum T mit n Knoten, in denen die Schl¨ussel S = {s1 , s2 , . . . , sn } gespeichert sind. Der AVL-Baum sei entstanden, indem die Schl¨usselmenge S in einer bestimmten Reihenfolge in einen anf¨anglich leeren Baum eingef¨ugt wurden. In der Regel m¨ussen hierbei einige Rotationsoperationen durchgef¨uhrt werden. Gibt es zu jedem solchen Baum T eine Einf¨ugereihenfolge der Schl¨usselmenge S, die zum gleichen AVL-Baum T f¨uhrt, jedoch keine einzige Rotation notwendig macht? Beweisen oder widerlegen Sie Ihre Vermutung.
Aufgabe 3.9 Wie ist beim Einf¨ugen eines Schl¨ussels in einen B-Baum der Ordnung 7 vorzugehen, wenn der Knoten, der den neuen Schl¨ussel aufnehmen soll, bereits 6 Schl¨ussel enth¨alt? Erkl¨aren Sie den Vorgang und zeichnen Sie eine entsprechende Skizze.
Aufgabe 3.10 F¨ugen Sie die Folge h1, 2, 3, 4, 15, 14, 7, 8, 9, 12, 11i in genau dieser Reihenfolge in einen anfangs leeren B-Baum der Ordnung 4 ein. Zeichnen Sie den B-Baum jeweils nach dem Einf¨ugen eines Schl¨ussels. F¨ugen Sie nun die Schl¨ussel in einen AVL-Baum und dann in einen Bin¨aren Suchbaum ein und zeichnen Sie diese. Vergleichen Sie anhand Ihrer Ergebnisse die drei Baumarten.
