Transcript
C. Sohler M. Bury, A. Krivo²ija D. Mezlaf, A. Rey
SoSe 2016 DAP2 Heimübung 10
Ausgabedatum: 10.6.2016 Abgabedatum: Fr. 17.6.16 (Mo. 20.6. für Gruppen 28-32) 12 Uhr Abgabe: Schreiben Sie unbedingt immer Ihren vollständigen Namen, Ihre Matrikelnummer und Ihre Gruppennummer auf Ihre Abgaben! Beweise sind nur dort notwendig, wo explizit danach gefragt wird. Eine Begründung der Antwort wird allerdings immer verlangt. Aufgabe 10.1 (5 Punkte): AVL-Bäume Gegeben sei der folgende binäre Suchbaum T : 21 10
30 13
24
41 27
55
a) Veri zieren Sie, dass T ein AVL-Baum ist. b) Fügen Sie die Schlüssel 15, 50, 29, 12 in der genannten Reihenfolge in den Baum T so ein, dass die AVL-Eigenschaft erhalten bleibt. Geben Sie den AVL-Baum nach jeder Operation an. Geben Sie auÿerdem an, an welchen Knoten und in welche Richtung rotiert wird. c) Löschen Sie in T die Schlüssel 10, 27 und 41 in der genannten Reihenfolge. Geben Sie wiederum den AVL-Baum nach jeder Operation an und geben Sie auÿerdem an, an welchen Knoten und in welche Richtung rotiert wird. Binäre Suchbäume und Nachfolger Wir betrachten einen binären Suchbaum und die aufsteigend sortierte Folge der enthaltenen Schlüssel, die alle unterschiedlich sein sollen. Seien v, w Knoten im Baum und S(v), S(w) die entsprechenden Schlüssel der Knoten. Wir nennen w den direkten Nachfolger von v, wenn S(v) < S(w) gilt und es keinen Knoten w im Suchbaum gibt mit S(v) < S(w ) < S(w). Ferner bezeichnen wir ein Knoten v als anhänglich, wenn er der Vater oder ein Kind seines direkten Nachfolgers ist. Wir sind daran interessiert, ohne Zugri auf die sortierte Folge der Schlüssel die Anzahl der anhänglichen Knoten in einem binären Suchbaum zu nden. 1 Aufgabe 10.2 (5 Punkte):
0
0
a) Betrachten Sie einen binären Suchbaum der Höhe 2, der einen Knoten v und seinen direkten Nachfolger w enthält. Welche Eigenschaften müssen für die Kinder der Knoten v und w gelten, damit v anhänglich ist? b) Geben Sie einen Algorithmus an, der für einen gegebenen binären Suchbaum die Anzahl enthaltener anhänglicher Knoten zurückgibt. c) Analysieren Sie die Laufzeit Ihres Algorithmus. d) Beweisen Sie die Korrektheit Ihres Algorithmus. : Die volle Punktzahl gibt es für einen Algorithmus mit einer worstcaseLaufzeit von O(n) zusammen mit korrekter Laufzeitanalyse, mit n als Anzahl der im Suchbaum enthaltenen Knoten. Anmerkung zu b) und c)
2
