Prof. Dr. R. Laue                                                                                                                                  SS04
                                Informatik IV
                                Übungsblatt 3
                                Abgabe: 13.5.04  nach der Vorlesung

URL:         /axel/informatik4_ss04_blatt3.html
Dieses  Übungsblatt ist in Zweiergruppen zu bearbeiten. 

Aufgabe 5 B Baum /B* Baum

Wir betrachten einen B-Baum mit maximal  2k Einträgen.
a) Was ist die Minimalanzahl an Einträgen für einen Baum der Höhe n. (2 Punkte)
b) Was ist die Maximalanzahl an Einträgen für die Höhe n. (2 Punkte)
Sei nun k=1
c) Geben Sie eine Beispiel-Eingabefolge an um aus einem leeren Baum einen Beispielbaum für a) im Fall n=3  zu bekommen (2 Punkte)
d) Geben Sie eine Beispiel-Eingabefolge an um aus einem leeren Baum einen Beispielbaum für b) im Fall n=3  zu bekommen (2 Punkte)
e) Verallgemeinern Sie c) und d) für beliebiges n,k. (2 Extrapunkte)

Zum Ausprobieren sei auf den link http://www.aifb.uni-karlsruhe.de/Lehrangebot/Sommer1997/dbis2/BBaum.html verwiesen.

Im Fall des B* Baums sind die eigentlichen Einträge nur in der untersten Ebene. Wir betrachten wieder einen Baum mit maximal 2k Schlüsseln. Bei der Höhe des B* Baums zählen wir nur die Ebenen der inneren Knoten.
f) Was ist die Minimalanzahl an Einträgen für einen Baum der Höhe n. (2 Punkte)
g) Was ist die Maximalanzahl an Einträgen für die Höhe n. (2 Punkte)

Aufgabe 6 (2 + 2 Punkte)

Bei mehrdimensionsalen Suchbäumen kann man beim Löschen die Strategie verfolgen benachbarte Hyperrechtecke zu einem neuem  größeren Hyperrechteck zusammenzufassen. Zeigen Sie wie dieser naive Ansatz bereits im dreidimensionalen Fall zu einer Verklemmung (d.h. man findet kein Paar  zum Zusammenfassen) führen kann.  (2 Punkte) Schlagen Sie eine Verbesserung des Algorithmus vor (zusätzliche Anforderung an das Paar, welches verschmolzen wird) und zeigen Sie wie dadurch  das Problem vermieden wird. (2 Punkte)