WS 2002/2003                   Übung 11                          H. Schweppe
                                        

        Ausgabe: 10.1.12. 2002
        Abgabe:   21. 1. 2003  15.00

Aufgabe 11.1 (  9 P)

a) (3 P)  Fügen Sie die folgenden Schlüssel in dieser Reihenfolge in eine Sprungliste ein: E A S Y Q U  T I O N.    
     Die Zufallsfolge sei: 1  001 1 1 01 01 1 0001 1 1   (1 = kein Kopieren des Schlüssel in die Indexliste L_i+1)

b)  (6 P) Für Skip-Listen  soll eine Operation atRank(int i) entworfen und als Pseudocode implementiert werden, die den Schlüssel an der Position (0 .. n-1)   in der "primären"  Liste L₀ liefert. Dazu muss evtl. die Datenstruktur geändert werden. Die Operation soll  O(log n) Zeitbedarf haben. (Zeigen!) 

Aufgabe 11. 2 (15 P)

a) (3 P) Fügen Sie in einen anfangs leeren B-Baum (t = 2, also (2.4)-Baum) die Schlüssel e a s y q u e s t i o n  in dieser Reihenfolge ein (jeweils einen Buchstaben).

b) (1 P) Wie viele Schlüssel können in einem B-Baum mit Grad t und Höhe h maximal gespeichert werden?

c) (1 P) Wie findet man den Schlüssel mit dem kleinsten Wert in einem B-Baum?

d) (2 P) Wie findet man den Vorgänger eines Schlüssels in einem B-Baum? (Peudocodealgorithmus) 

e) (2 P) Ein (2,4)-Baum enthält 100000 Schlüssel. Wie hoch ist der Baum mindestens / höchstens?  (Begründung nicht vergessen).

f)  (3 P) Gesucht ist die minimale Anzahl von Schlüsseln, die man in einen 2-3-Baum einfügen muss, so dass beim Einfügen des letzten Schlüssels mehrere Spaltungen nötig werden. 

g)  (3 P) Gegeben der folgende (2,4)-Baum. Führen Sie folgende Operationen in dieser Reihenfolge durch: 
   insert(h), insert(f), insert(b), insert(d), delete(d), delete(j).  Zeichnen Sie den Baum nach jeder Operation sowie nach Teiloperation 
  (Knoten spalten, verschmelzen, etc). 

Aufgabe 11.3 ( 6P)
a) (4 P) Implementieren Sie die Operation delete für binäre Suchbäume.
boolean delete (Comparable v)
// pre: Knotenwerte sind eindeutig
// post: wenn Knoten mit dem Wert v gefunden wurde, wird der Knoten gelöscht,
// sonst bleibt der Baum unverändert. 
// result: true, wenn ein Knoten gelöscht wurde, false sonst.

Gehen Sie von Ihrer Suchbaumimplementierung in Aufgabe 9.4 aus oder ergänzen Sie die folgende 'quick-and-dirty'-Implementierung. Wie üblich gehören Tests zur Lösung der Aufgabe.

b) (2 P) Gesucht ist die Methode  search(Comparable v) für die   B-Baum-Klasse class BTreeN, die in der VL angegeben wurde (F. 6). (Trockenprogrammierung).

30 Punkte