Aufgabe 22 (5 Programmierpunkte - Abgabe per email bis 9.7. 10.00 Uhr)
Lösen Sie Teilaufgabe 19.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.

mittels der vorgestellten Routine tfind(), tsearch(), tdelete(), twalk(). Diese Aufgabe muß auf einem UNIX Rechner gelöst werden.

Aufgabe 23 (10 Programmierpunkte - Abgabe per email bis 9.7. 10.00 Uhr)
Die Datenstruktur Knoten der bisherigen Programmieraufgaben 13,16,19 soll modifiziert werden um Rot-Schwarz-Bäume zu implementieren.
Die Routinen zur Ausgabe und Rotation sollten weiterfunktionieren. Aber dabei auf Farbänderungen (bzw Rangänderungen) achten.

1) Realisieren Sie das Einfügen in den Rot-Schwarz-Baum. Verwenden Sie dazu die Tabelle aus Aufgabe 18.
2) Füllen Sie im main Programm den Baum mit 1000 zufälligen Zahlen (ohne Duplikate) bevor Sie die print Routine aufrufen.
 
 

Aufgabe 24 (2+2+2 Punkte)
1) Zeigen Sie daß in einem (a,b) Baum die Anzahl der Blätter um 1 größer ist als die Anzahl der abgespeicherten Werte.
2) Was ist die minimale Anzahl der Werte in einem (a,b) Baum der Höhe n?
3) Wie kann ein solcher Werte-minimaler Baum erreicht werden?
 

 
Aufgabe 25 (3 Punkte)
Man gebe ein Beispiel eines B Baums (mit a = 3), der die Höhe 2 besitzt und durch Einfügen eines weiteren Elements die Höhe vergrößert.