Algorithmen und Programmierung III 

         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