Hinweis: Voraussetzung für diese Aufgabe ist Kapitel 10 (B-Bäume, Freitag in der Vorlesung).
Wir betrachen in dieser Aufgabe minimal gefüllte B-Bäume:
- Wieviele Schlüssel fasst ein B-Baum der Höhe h mindestens?
- Ein minimal gefüllter B-Baum enthalte n gespeicherte Schlüssel. Wieviele Schlüsselvergleiche werden bei einer Suche im Worst Case durchgeführt? Begründen Sie. Sie können hierbei annehmen, dass die Knoten des Baums linear durchsucht werden.