WS 97/98: Algorithmen und Programmierung III - Übungsblatt 10
Abgabe bis 22.1., 12.30 Uhr
[ Aufgabe 10.1, optional ] (7 Punkte)
a) Repräsentiere geordnete Mengen als B*-Bäume in Miranda oder Modula
und implementiere die Einfüge-Operation! (Hinweis: Gesplittet werden sollte
erst dann, wenn von zwei benachbarten vollen Knoten einer
überläuft; die zwei Knoten können dann durch drei Knoten ersetzt werden.)
b) Welches sind die Vor- und Nachteile von B*-Bäumen gegenüber B-Bäumen?
Hinweis: Für die Gestaltung der Wurzel sind verschiedene Versionen
denkbar. Beispielsweise kann man (für eine natürliche Zahl k) festlegen:
Knotengröße 3k, Wurzelgröße 6k.
Aufgabe 10.2 (4 Punkte)
Wir betrachten geordnete Mengen, die als Suchbäume repräsentiert werden.
Eine solche Menge M habe die Kardinalität n.
Zur Erinnerung:
1. M kann als vollständiger Binärbaum repräsentiert werden. Gleichlange Wege von der
Wurzel zu allen Blättern sind aber nur dann möglich, wenn n=2^k-1 für eine
natürliche Zahl k.
2. In einem 2-3-Baum sind stets alle Wege von der Wurzel zu einem Blatt
gleich lang.
Beweise, ohne die Existenz einer die Invariante erhaltenden Einfügeoperation
vorauszusetzen: Jede Menge - egal welcher Kardinalität - kann als
2-3-Baum repräsentiert werden.
Aufgabe 10.3 (5 Punkte)
Repräsentiere geordnete Mengen als 2-3-Bäume in Miranda und gib Funktionen für das
Suchen und Einfügen an!
13.1.1998