Heimübungsblatt 10

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) Verizieren 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

Download Report