Nabend!
Kann mir jemand sagen, was passiert, wenn in einem B-Baum die Wurzel gelöscht werden soll? Sagen wir, die Wurzel ist einelementig (zB 48)…wird dann wie beim Löschen in einem inneren Knoten verfahren? Im Cormen steht auch nix darüber drin…

Nabend!
Kann mir jemand sagen, was passiert, wenn in einem B-Baum die Wurzel gelöscht werden soll? Sagen wir, die Wurzel ist einelementig (zB 48)…wird dann wie beim Löschen in einem inneren Knoten verfahren?

Wäre das denn problematisch? Ich denke, die Wurzel wird dann wie sonst auch entweder durch das größte Element im linken Teilbaum (TREE-PREDECESSOR im Cormen) oder das kleinste im rechten Teilbaum (TREE-SUCCESSOR im Cormen) ersetzt, je nachdem, wie sich der Entwickler das gerade gedacht hat. Da dieses Element dann aus einem Blattknoten kommt, kann es einen Unterlauf auslösen, der ganz normal behandelt werden muss (ausgleichen oder mergen).

Im Cormen und auf Wikipedia steht, dass die maximale Anzahl von Schlüssel pro Knoten 2k-1 ist, während im GDB-Skript die Größe auf 2k beschränkt ist. Ist das Auslegungssache oder hat sich irgendwo ein Fehler eingeschlichen? Ist ja nicht ganz unwichtig fürs Einfügen. Außerdem unterscheidet sich die Mindestgröße auch in den verschiedenen Quellen….

Im Cormen und auf Wikipedia steht, dass die maximale Anzahl von Schlüssel pro Knoten 2k-1 ist, während im GDB-Skript die Größe auf 2k beschränkt ist. Ist das Auslegungssache oder hat sich irgendwo ein Fehler eingeschlichen?

Hmm, vermutlich wird das Auslegungssache sein. Eine gerade Maximalanzahl von Einträgen pro Knoten hat aber den Vorteil, dass man beim durch einen Überlauf beim Einfügen ausgelösten Split-Vorgang genau das mittlere Element hochziehen kann, da der Überlauf bei 2k+1 Einträgen stattfindet. Ansonsten hätte man zwei mittlere Elemente zur Auswahl, das wäre ja schrecklich.