Aufgabe 19 (10 Programmierpunkte - Abgabe per email bis 2.7. 10.00 Uhr)
Erweitern Sie das Programm aus Aufgabe 13 und 16  um folgende Punkte:
1. Es soll das Löschen im  AVL Baum  programmiert werden.
2. Schreiben Sie ein find, welches einen Zeiger auf den gefundenen Wert zurückgibt, bzw NULL wenn der Wert noch nicht da ist.
3. Erzeugen Sie im main Programm 10000 zufällige Zahlen zwischen 1 und 1000, schauen Sie mit find ob dieser Wert schon im Baum ist. Wenn ja soll er gelöscht werden, wenn nein soll er eingefügt werden. Danach rufen Sie Ihre print Routine auf.

Aufgabe 20 (4 + 2 Punkte)
Der Vorteil der  Rot-Schwarz-Bäume ist das Verhalten beim Löschen. Es sind maximal 3 (Doppel)Rotationen nötig. Geben Sie ein Beispiel an wo, dies nötig ist. Zeigen Sie die Operationen beim Löschen.  (4 Punkte) Geben Sie eine Eingabefolge an, die zu diesem Baum führt. (2 Punkte)

Aufgabe 21 (8 Punkte)
Beschreiben Sie das Löschen 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