B Baum

Moderator: AI 2

mehdiB
Neuling
Neuling
Beiträge: 2
Registriert: 4. Dez 2015 14:25

B Baum

Beitrag von mehdiB » 2. Feb 2016 15:57

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

steffen12
Moderator
Moderator
Beiträge: 205
Registriert: 14. Okt 2009 16:28

Re: B Baum

Beitrag von steffen12 » 3. Feb 2016 01:33

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

Antworten

Zurück zu „AI 2“