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.