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 21 (7 Punkte)
Beschreiben Sie das Löschen  in einem 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 22 (3 Punkte)
Ein Vorteil des RS Baums gegenüber dem AVL Baum ist das bessere Verhalten beim Löschen. Ein RS Baum benötigt  maximal 3 Rotationen beim Löschen. Geben Sie ein Beispiel an wo diese auch wirklich benötigt werden.

Aufgabe 23(12 Punkte Programmieraufgabe bis 28.6.2001)
Erweitern Sie das Programm aus Aufgabe 20 um folgende Routinen:
 

1. Löschen in dem RS-Baum unter Verwendung der Tabelle aus 21
2. Fügen Sie wie in Aufgabe 20 1000 zufällige Werte zwischen 1 und 1000 ein, löschen Sie danach 1000 zufällige Werte zwischen 1 und 1000
und geben Sie dann den Baum aus.