Frage:
Gegeben sei ein aufsteigend geordneter B-Baum T der Ordnung m = 4 mit Wurzel w,
insgesamt n Knoten und Höhe h. In jedem inneren Knoten v sind i Schlüssel vom Typ
Integer in dem Array v.keys gespeichert, 0 < i < 4. Es bezeichne s.left bzw. s.right den
linken bzw. rechten Sohn von Schlüssel s. Wenn der linke bzw. rechte Sohn ein Blatt ist,
ist s.left bzw. s.right gleich NIL. Sei außerdem v.parent der Vater von v.
(a) Zeichnen Sie alle möglichen B-Bäume der Ordnung m = 4 mit mindestens drei und
maximal vier Schlüsseln, wobei die Schlüssel 0, 1, 2 und ggf. 3 sind. Die B-Bäume
mit drei Schlüsseln sollen ohne den Schlüssel 3 gezeichnet werden
(b) Implementieren Sie in Pseudocode eine Funktion third_smallest(T), die in O(h) den
Wert des drittkleinsten Schlüssels von T zurückgibt. Sie dürfen davon ausgehen, dass
T drei oder mehr Schlüssel besitzt. Begründen Sie, warum die geforderte Laufzeit
eingehalten wird.
für a) habe ich nur 2 Bäume
