Aufgabe 16 (10 Programmierpunkte - Abgabe per email bis 25.6. 10.00 Uhr)
Erweitern Sie das Programm aus Aufgabe 13 um folgende Punkte:
1. Es sollen die für AVL Bäume nötigen Rotationen programmiert werden.
2. Das aus Aufgabe 13 bekannte insert_baum soll einen AVL Baum anlegen, diesmal inklusive  Balancier Operationen. Dabei ist es nötig, die Datenstruktur Knoten um eine Komponente zu erweitern, damit die Balancieroperationen funktionieren.
3. Füllen Sie im main Programm den Baum mit 1000 zufälligen Zahlen bevor Sie die print Routine aufrufen.

Aufgabe 17 (4 Punkte)
Um sich mit den Rot-Schwarz-Bäumen vertraut zu machen, sollen die Buchstaben aus dem Wort PFERDESTALL in einen RS-Baum eingefügt werden (nur auf dem Papier). (zuerst das P) Ist der jeweilige Buchstaben schon da, so soll dieser nicht eingefügt sondern gelöscht werden. Visualisieren Sie die einzelnen Schritte in der aus der Vorlesung bekannten Weise.

Aufgabe 18 (8 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