Nabla - B-Tree remove

mackeroni7
Neuling
Neuling
Beiträge: 4
Registriert: 17. Sep 2016 16:39

Nabla - B-Tree remove

Beitrag von mackeroni7 » 17. Sep 2016 16:47

Hallo alle zusammen,
könnte mir jemand erklären, wie die Lösung auf dem Screenshot zustande kommt?
Ich dachte nämlich, dass der Zeiger p nicht auf/über einen Knoten im B-Baum darf, der weniger als M Elemente hat.
btreeRemove.png
btreeRemove.png (34.38 KiB) 517 mal betrachtet

mackeroni7
Neuling
Neuling
Beiträge: 4
Registriert: 17. Sep 2016 16:39

Re: Nabla - B-Tree remove

Beitrag von mackeroni7 » 17. Sep 2016 16:52

Hier nochmal die Bilder einzeln, wegen der schlechten Qualität.
Dateianhänge
aufgabe.png
aufgabe.png (23.46 KiB) 516 mal betrachtet
loesung.png
loesung.png (15.4 KiB) 516 mal betrachtet

mackeroni7
Neuling
Neuling
Beiträge: 4
Registriert: 17. Sep 2016 16:39

Re: Nabla - B-Tree remove

Beitrag von mackeroni7 » 17. Sep 2016 17:00

Und nochmal mit imgur:
Aufgabe: http://imgur.com/a/8cpBF
Lösung: http://imgur.com/a/JcYpK

yokop
Windoof-User
Windoof-User
Beiträge: 28
Registriert: 13. Apr 2016 12:49

Re: Nabla - B-Tree remove

Beitrag von yokop » 17. Sep 2016 17:05

Der Zeiger befindet zeigt zu Beginn auf die Wurzel (hier benötigt man nach Invariante nicht mehr als M-1 keys).
Dann wird zu dem Knoten mit Schlüsselwerten 69, 88 hinabgestiegen, aus welchem man löschen könnte, also ist nichts zu tun.
Dann zum Knoten mit 51, 55. Auch kein Problem. Hier wird dann der Schlüsselwert gefunden. Löschen heißt ersetzen durch den direkten Vorgänger, also wird die 55 aus dem Blatt nach oben an die Stelle der anderen 55 geschoben und das Element wurde gelöscht.

mackeroni7
Neuling
Neuling
Beiträge: 4
Registriert: 17. Sep 2016 16:39

Re: Nabla - B-Tree remove

Beitrag von mackeroni7 » 17. Sep 2016 18:47

Auszug aus dem Algo-Wiki:
Invariante:
(...)
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.

http://wiki.algo.informatik.tu-darmstad ... ee:_remove

yokop
Windoof-User
Windoof-User
Beiträge: 28
Registriert: 13. Apr 2016 12:49

Re: Nabla - B-Tree remove

Beitrag von yokop » 18. Sep 2016 08:26

Hm, gute Frage... Also im TranscriptBTree steht zusätzlich: Wenn ein Knoten, zu dem hinabgestiegen werden soll, dies nicht erfüllt...

Antworten

Zurück zu „Archiv“