Die Aufgaben sollen in Zweiergruppen bearbeitet werden. Dreiergruppen sind nicht zulässig
Jede Aufgabe soll  auf einem Extrablatt bearbeitet werden. Bitte auf jedem Blatt Name/Matrikelnummer notieren.
 

Aufgabe 18 (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 19 (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 20(8 Punkte Programmieraufgabe bis 21.6.2001)
Erweitern Sie das Programm aus Aufgabe 17 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 19
3. Fügen Sie wie in Aufgabe 13 1000 zufällige Werte ein und geben Sie den Baum aus.