Prof. Dr. R. Laue                                                                                                                                  SS01
                                Informatik II
                                Übungsblatt 9
                                            Abgabe: 28.6.01 in der Vorlesung
URL:         /axel/informatik2_ss01_blatt9.html
 
 

Die Aufgaben sollen in Zweiergruppen bearbeitet werden. Dreiergruppen sind nicht zulässig
Jede Aufgabe soll  auf einem Extrablatt bearbeitet werden. Bitte auf jedem Blatt Name/Matrikelnummer notieren.
 
 

Aufgabe 24 (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 25 (3 Punkte)
Man berechne die Änderung der Balance für die Knoten eines BB[] Baums, die durch eine Doppelrotation verursacht wird.
 
 
Aufgabe 26 (4 Punkte)
Beschreiben Sie den Aufbau eines (a,b) Baums bei der Eingabe aufsteigend sortierter Daten.