B-Tree remove: Mehrfachvorkommen von Schlüsseln

mdk
Mausschubser
Mausschubser
Beiträge: 43
Registriert: 18. Apr 2014 10:33

B-Tree remove: Mehrfachvorkommen von Schlüsseln

Beitrag von mdk » 4. Jul 2017 16:39

Hallo,

wenn gefordert ist, dass man Schlüssel x löschen soll, x aber mehrfach in dem B-Baum vorkommt (z.B. in einem inneren Knoten und in einem Blatt), welchen Schlüssel soll man dann löschen?

Danke vorab für eine Antwort.

Benutzeravatar
SophiaLi1
Kernelcompilierer
Kernelcompilierer
Beiträge: 542
Registriert: 5. Jan 2014 11:48

Re: B-Tree remove: Mehrfachvorkommen von Schlüsseln

Beitrag von SophiaLi1 » 18. Jul 2017 13:35

Push.

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

Re: B-Tree remove: Mehrfachvorkommen von Schlüsseln

Beitrag von steffen12 » 31. Jul 2017 17:11

Hallo,

ist der Schlüssel in einem Blatt, wird er dort gelöscht.
Allgemein gesprochen wird immer das zuletzt gesehene Vorkommen gelöscht.

Bitte lesen sie dies:
https://wiki.algo.informatik.tu-darmsta ... ee:_remove

Dort seht insb. in der Beschreibung des Induction Step:

Abstract view:
If a leaf is reached:
1. If K is in that leaf, remove it.
2. Otherwise, if K has already been seen, overwrite the found occurrence of K with its immediate predecessor (which is p.keys[p.n] ).
3. Terminate the algorithm.

Antworten

Zurück zu „Archiv“