Invariante B-Tree: remove

joneswack
Neuling
Neuling
Beiträge: 8
Registriert: 14. Sep 2013 12:09

Invariante B-Tree: remove

Beitrag von joneswack »

Laut Wiki heißt es in der Invariante von B-Tree: remove unter Punkt 5:
If p points to the root, at least two keys are currently stored in the root; otherwise, at least M keys are currently stored in the node to which p points.

Das würde ja bei einem Baum der Ordnung M = 2 bedeuten, dass ich den Baum umsortieren muss, in dem Moment, wo p auf einen Knoten zeigen würde, der weniger als 2, also nur einen besetzten Keyslot hat.

Nun stellt man sich mal einen Baum aus 3 Knoten mit M = 2 vor.
Oberer Knoten [200| | ]
Linker Knoten [75|100| ] Rechter Knoten [350| | ]

Hier müsste ich also gemäß der Invariante der Löschoperation den Baum direkt an der Wurzel umformen. Ein Merge ist nicht möglich, weil links mehr als ein Slot besetzt ist. Ein Shift nach rechts wäre möglich, würde aber in der Wurzel nur dafür sorgen, dass die 200 durch die 100 ersetzt würde.
Intuitiv würde ich, wenn ich die 350 löschen wollte, einen Shift nach rechts durchführen, sodass wenigstens die allgemeine B-Tree Invariante nicht verletzt würde. Aber die Invariante der Löschoperation ist hier nicht einzuhalten, oder habe ich da etwas falsch verstanden?

In den Vorlesungsvideos wird ja ebenfalls das eher intuitive Verfahren verwendet, dessen Invariante laut Bemerkung im Wiki komplizierter aufzuschreiben wäre.

robertH
Mausschubser
Mausschubser
Beiträge: 58
Registriert: 29. Apr 2013 13:11

Re: Invariante B-Tree: remove

Beitrag von robertH »

In der Tat muss und wird ein Rechtsshift in der Induktionsbasis durchgeführt. Wichtig ist hierbei zur Erfüllung der Invariante die Kleinigkeit, dass p nach dem Rechtsshift direkt so initialisiert wird, dass es direkt auf den Kinderknoten zeigt in den wir zum Löschen herabsteigen möchten (letzer Punkt p:= p.children[1]) und in diesem sind nun aufgrund des Rechtsshifts 2 also M Elemente vorhanden.

joneswack
Neuling
Neuling
Beiträge: 8
Registriert: 14. Sep 2013 12:09

Re: Invariante B-Tree: remove

Beitrag von joneswack »

Ah vielen Dank! Ja so ergibt es Sinn. Ich nehme mal an, dass der Abstieg von p ebenfalls mit der Merge-Operation erfolgt.
Die unterschiedlichen Varianten aus Vorlesungsvideos und Wiki haben mich leicht verwirrt.

Antworten

Zurück zu „Archiv“