Seite 1 von 1

B Baum

Verfasst: 2. Feb 2016 15:57
von mehdiB
Hallo
Ich habe ein paar mal die foo aufgaben gemacht und ich verstehe gar nicht bei B Baüme ( remove ) wann man die Merge methode verwenden soll und wass die Shift key to sibling , da manchmal der Shift to key sibling methode erwartet wird , jedoch wenn ich die Merge methode verwende , komme ich auch auf eine vollständige B Baum wurde aber von foo als falsch bewertet . Vllt habe ich den Unterschied nicht gut verstanden , wenn man das erklären könnte wäre super .
Danke im vorraus
LG

Re: B Baum

Verfasst: 3. Feb 2016 01:33
von steffen12
Die Ausgangssituation ist in beiden Fällen im Grunde gleich: Der Knoten zu dem der Pointer p hinabsteigen sollte, hat nur die minimale Anzahl von Schlüsseln (n = M - 1). D.h. würde p dorthin absteigen, würde p auf einen Knoten zeigen in dem kein Schlüssel gelöscht werden kann, ohne die B-Baum-Eigenschaften zu zerstören. Daher wird vorher korrigiert.

Es gibt zwei Fälle:
1) Der Nachbarknoten* dieses Knotens (mit zu wenig Schlüsseln) hat genau die minimale Anzahl von Schlüsseln -> Merge kommt zu Einsatz.
2) Der Nachbarknoten* hat mehr als die minimale Anzahl von Schlüsseln -> Mittels Shift_Key_to_Sibling werden Schlüssel von dort in den betreffenden Knoten rotiert.

* Wichtig: Es wird immer der rechte Nachbarknoten betrachtet, wenn dieser existiert. Andernfalls der linke.

In Fall 1 erhält man durch die Vereinigung einen Knoten mit n = 2M - 1 Schlüsseln (voll).
In Fall 2 hat der betreffende Knoten nun M Schlüssel, somit kann wieder einer gelöscht werden (falls nötig).
Der Zeiger p kann also nun hinabsteigen, und der Algorithmus kann fortgesetzt werden.

Viele Grüße,
Steffen