WS
2002/2003 Übung 10
H. Schweppe
Ausgabe: 19.12. 2002
Abgabe: 14. 1. 2003 15.00
Aufgabe 10.1 ( 6 P)
Gegeben der folgende Baum:
a) (1 P) Handelt es sich um einen AVL-Baum? Wenn nein, transformieren Sie ihn so, dass er die Balanceeigenschaft von AVL-Bäumen hat.
b)
(5 P) Führen Sie auf dem obigen (ggf. transformierten) AVL-Baum folgende Operationen
jeweils einzeln (also jeweils auf dem ursprünglichen Baum) aus :
add (1), add (15), delete (4) delete(8)
(Natürlich so, dass der Baum nach der jeweiligen Operation die
AVL-Baum-Invarianten wieder erfüllt). Bekanntlich wird wie in binären
Suchbäumen gelöscht bzw. hinzugefügt, ggf. mit anschließender Rotation um
die Höhenbalance wiederherzustellen.
Aufgabe 10.2 ( 7 P)
Geben Sie ein Beispiel für einen AVL-Baums an, bei dem beim Löschen eines
Knotens Q(log
n) Rotationen (Rebalancierungsoperationen), beginnend an einem Blattknoten bis zur Wurzel,
stattfinden. (Die nicht betroffenen Teile des Baums können als Dreiecke
symbolisiert werden.) Hinweis: verwenden Sie mindestens einen Baum der Höhe
5.
Aufgabe 10.3 ( 6 P)
Schreiben Sie ein möglichst effizientes Programm (Java oder Haskell), das für einen Binärbaum
entscheidet, ob es er die AVL-Baum-Invarianten erfüllt. Geben Sie eine Laufzeitabschätzung
an.
Aufgabe 10.4 ( 7 P)
Gesucht ist eine Abschätzung im Mittel für eine nicht erfolgreiche Suche in
einem binären Suchbaum. Jede Suche endet also in einem externen (leeren) Knoten
.
Hinweise:
- Gehen Sie von der in der Vorlesung abgeleiteten mittleren Pfadlänge M(n) für
alle
binären Suchbäume mit n Knoten aus. Sie beträgt bekanntlich:
M(n) = 2*(n+1) * Hn - 4n ,
mit Hn = ln n + g,
g = Eulersche
Konstante, Hn harmonische Reihe.
- Beachten Sie die Beziehung zwischen der Anzahl interner und externer
Knoten.
Aufgabe 10.5 (6
P)
Lösen Sie die Rekurrenzgleichung für die mittlere innere Pfadlänge von
binären Suchbäumen mit n Knoten durch sukzessives Einsetzen:
M(1) = 0
M(2) = 1
M(n) = (2*n - 2 + (n+1)* M(n-1) ) / n
für n > 2
Hinweis:
Lösung der Rekurrenz siehe 10.4. Bestimmen Sie M(n) / (n+1), M(n-1)/n ,
M(n-2)((n-1),...
und setzen Sie nacheinander ein.
32 Punkte