B-Tree: delete, mehrere gleiche Schlüssel

NonStop
Mausschubser
Mausschubser
Beiträge: 73
Registriert: 18. Apr 2015 19:15

B-Tree: delete, mehrere gleiche Schlüssel

Beitrag von NonStop »

Wie erkennt man welchen Schlüssel man löschen soll, wenn es mehrere sind? Z.B.:
Bild
und
Bild

Mit dem Pfeil ist der nach Musterlösung zu löschende Schlüssel gekennzeichnet.

Benutzeravatar
luedecke
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 124
Registriert: 17. Mär 2015 00:08

Re: B-Tree: delete, mehrere gleiche Schlüssel

Beitrag von luedecke »

Vorweg: Dieser Fall ist kein Fehler und durchaus beabsichtigt.

Diese Frage wurde mir heute schon öfters gestellt...

Hinweis: Das ergibt sich durch die Spezifikation des Algorithmus (s. Wiki) selbst ;)

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

Re: B-Tree: delete, mehrere gleiche Schlüssel

Beitrag von steffen12 »

Einen Schlüssel in einem B-Baum zu löschen bedeutet, ein Vorkommen dieses Schlüssel aus der Datenstruktur zu entfernen. Welche Instanz gelöscht wird, ist dabei immer eindeutig.
Das erste* Vorkommen wird entweder direkt entfernt, oder durch seinen unmittelbaren Nachfolger* überschrieben.
* Hinsichtlich der Totalordnung auf der Schlüsselmenge.

Es wird niemals in einem inneren Knoten einfach gelöscht, sondern immer überschrieben.
Das untere Bild zeigt jedoch, dass nach der Reorganisation des Baumes durch merge und shift_key_to_sibling das Ergebnis einen täuschenden Eindruck vermitteln kann.

Grüße, Steffen

Antworten

Zurück zu „Archiv“