Prof. Dr. R. Laue                                                                                                                                  SS98
                                Informatik II
                                Übungsblatt 9
                                Abgabe: 9.7. bis 10.00 Uhr
 
URL:         /axel/informatik2_ss98_blatt9.html
Dieses  Übungsblatt  ist in Zweiergruppen  zu bearbeiten.

Aufgabe 26 (4 Punkte)
Ein dreidimensionaler kd-Baum soll verwendet werden um einen Würfel in 27 Teilwürfel zu zerlegen. Beschreiben und zeichnen Sie den Baum.

Aufgabe 27 (10 Programmierpunkte - Abgabe per email bis 16.7. 10.00 Uhr)
Man kompletiere  die Implementation der Rot-Schwarz-Bäume.
1) Realisieren Sie das Löschen im Rot-Schwarz-Baum. Verwenden Sie dazu die Tabelle aus Aufgabe 21.
2) Füllen Sie im main Programm den Baum mit 1000 zufälligen Zahlen (ohne Duplikate) bevor Sie die print Routine aufrufen.
3) In Aufgabe 20 wurde ein Beispiel mit 3 Rotationen beim Löschen angegeben. Testen Sie dieses, verwenden Sie dabei eine Variante der print Funktion, die Farbe und Ebene mit ausgibt.

Aufgabe 28 (6 Punkte)
Bei der Bildbearbeitung stellt sich das Problem mit 256 Farben ein Bild möglichst farbgetreu darzustellen.  Die Farben im Ausgangsbild werden mit 24 Bit dargestellt. 8 Bit für jeweils rot, grün, blau (=RGB). Im bearbeiteten  Bild sollen nur noch 8 Bit pro Bildpunkt verwendet werden. Diese 8 Bit sind ein Offset in die sogenannte Farbpalette, wo zu jeder der 256 möglichen Farben die RGB Werte mit 24 Bit kodiert sind. Entwerfen Sie einen Algorithmus, der eine möglichst farbgetreue Darstellung erlaubt. Tip: dreidimensionaler kd-Baum
 
Aufgabe 29 (4 Punkte)
Man wähle Namen von acht Mathematikprofessoren der Uni Bayreuth und die eigenen Namen, und sortiere diese Namen mittels Bucketsort. Man verwende die Variante ohne Präprozessing.