Prof. Dr. R. Laue                                                                                                                                  SS00
                                Informatik II
                                Übungsblatt 7
                                            Abgabe: 22.6.00 bis 10.00 Uhr in der Vorlesung
URL:         /axel/informatik2_ss00_blatt7.html

Die Programmieraufgaben sind alleine zu bearbeiten, die anderen Aufgaben können in Zweiergruppen bearbeitet werden.

Aufgabe 13 (6 Punkte)
Geben Sie einen AVL Baum der Höhe 2n an, der beim Löschen eines geeigneten Blattes n Rotationen benötigt. Beweis!
 

Aufgabe 14 (6 Punkte)
Beschreiben Sie das Einfügen in einen Rot Schwarz Baum indem Sie in Tabellenform angeben, welche Zeiger unter welchen Bedingungen wie umgelegt werden müssen. Listen Sie dabei auch die zugehörigen Rangänderungen auf.
Muster für die Tabelle:
 
Bedingung Zeigeränderung Farbänderung Rangänderung Bild

Aufgabe 15 (8 Punkte Programmieraufgabe)
Erweitern Sie das Programm aus Aufgabe 12 um folgende Routinen:
1. Weiterer Eintrag in der Struktur (Rang bzw. Farbe) um einen RS Baum zu implementieren und Anpassen der Rotationsroutinen.
2. Einfügen in den RS-Baum unter Verwendung der Tabelle aus 14
3. Fügen Sie wie in Aufgabe 9 1000 zufällige Werte ein und geben Sie den Baum aus.