Die Programmieraufgaben sind alleine zu bearbeiten, die anderen Aufgaben können in Zweiergruppen bearbeitet werden.
 

Aufgabe 19 (3+3 Punkte)
Man diskutiere, wie sich ein Rot-Schwarz Baum durch Zusammenfassen von geeigneten Knoten in einen (a,b) Baum überführen läßt.
Man vergleiche die Balancieroperationen, die beim Einfügen in den Rot Schwarz Baum und in den entsprechenden (a,b) Baum erforderlich werden.
 
 

Aufgabe 20 (3+4 Punkte)
Wieviele Werte liegen in einem Knoten eines (a,b) Baums, wenn beim Aufbau Zahlen in aufsteigender Reihenfolge eingegeben werden?
Beim Einfügen kann die Strategie verfolgt werden, Werte in die Nachbarknoten zu verschieben (wie beim Löschen). Man beschreibe den entsprechenden Algorithmus, wie ändert sich das Ergebnis aus dem ersten Teil dieser Aufgabe?