B-Tree Remove Unklarheit

Bei Postings zu Algorithmus X lassen Sie Ihren Betreff bitte mit
"X: " beginnen, bei allgemeinen Postings zu Nabla bitte mit "Nabla: ", jeweils gefolgt von einer möglichst präzisen Überschrift, danke!

Moderator: Algorithmen und Datenstrukturen

Forumsregeln
Bei Postings zu Algorithmus X lassen Sie Ihren Betreff bitte mit
"X: " beginnen, bei allgemeinen Postings zu Nabla bitte mit "Nabla: ", jeweils gefolgt von einer möglichst präzisen Überschrift, danke!
th3
Neuling
Neuling
Beiträge: 2
Registriert: 19. Apr 2016 14:36

B-Tree Remove Unklarheit

Beitrag von th3 » 15. Sep 2016 10:12

Hallo,

im folgenden Screenshot ist der Schritt 2 einer B-Tree remove Aufgabe zu sehen.
Der Schlüsselwert 97 soll entfernt werden.
Im ersten Schritt wurde die Wurzel gemerget, da die Kindknoten nur je 1 Schlüssel enthielten.
Warum wird nun aber im nächsten Schritt nochmals gemerget und nicht die 97 gelöscht?

Bild

Gruß

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

Re: B-Tree Remove Unklarheit

Beitrag von yokop » 15. Sep 2016 10:26

Das folgt aus der Invariante beim Löschen eines Elements in einem B-Tree. Es darf nur zu Knoten hinabgestiegen werden, wenn diese mehr als die minimale Anzahl an Knoten haben, also aus dem Knoten gelöscht werden könnte.

PhiRoh
Neuling
Neuling
Beiträge: 3
Registriert: 15. Sep 2016 18:33

Re: B-Tree Remove Unklarheit

Beitrag von PhiRoh » 15. Sep 2016 18:43

Guten Abend! Ich habe auch eine Frage dazu:
Bild 1.jpg
Bild 1.jpg (115.89 KiB) 614 mal betrachtet
Zeigt einen Schritt der Lösung in Nabla.

Meine Frage dazu lautete: Wieso genau nimmt er zwingend den rechten Geschwisterknoten?
Ich habe es mit dem Linken gemacht und komme deshalb auf eine alternative, meines Erachtens aber invarianteerfüllende, Lösung!
Was sagt ihr dazu? Nabla zeigt es auf jeden Fall als inkorrekte Lösung an.
Bild 2.jpg
Bild 2.jpg (77.35 KiB) 614 mal betrachtet

Vielleicht noch eine anschließende Frage zu "B-Tree remove" an Herr Prof. Weihe:
Wie muss man sich die gegebenen Daten zu dieser Poblemstellung in der Klausur vorstellen?
Bekommt man, wie in Nabla, die Kanten und Knoten und muss dann anhand dessen eine Lösung auf Papier basteln?

PhiRoh
Neuling
Neuling
Beiträge: 3
Registriert: 15. Sep 2016 18:33

Re: B-Tree Remove Unklarheit

Beitrag von PhiRoh » 16. Sep 2016 10:52

PhiRoh hat geschrieben:Guten Abend! Ich habe auch eine Frage dazu:

Bild 1.jpg

Zeigt einen Schritt der Lösung in Nabla.

Meine Frage dazu lautete: Wieso genau nimmt er zwingend den rechten Geschwisterknoten?
Ich habe es mit dem Linken gemacht und komme deshalb auf eine alternative, meines Erachtens aber invarianteerfüllende, Lösung!
Was sagt ihr dazu? Nabla zeigt es auf jeden Fall als inkorrekte Lösung an.

Bild 2.jpg


Vielleicht noch eine anschließende Frage zu "B-Tree remove" an Herr Prof. Weihe:
Wie muss man sich die gegebenen Daten zu dieser Poblemstellung in der Klausur vorstellen?
Bekommt man, wie in Nabla, die Kanten und Knoten und muss dann anhand dessen eine Lösung auf Papier basteln?

Meine Fragen haben sich erledigt! Es ist jetzt noch 2-3 mal die gleiche Situation aufgetaucht und es wurde tatsächlich stets der rechte Geschwisterknoten betrachtet!
Ich lass das Problem aber mal noch so im Forum stehen. (als Information)

Das mit der Lösung auf Papier basteln wird nach einigen Malen üben wohl auch funktionieren, wenn man durch sein eigenes Schriftbild durchblickt. :lol:

paprikawuerzung
Mausschubser
Mausschubser
Beiträge: 80
Registriert: 23. Mär 2014 23:33

Re: B-Tree Remove Unklarheit

Beitrag von paprikawuerzung » 16. Sep 2016 11:56

Ich bin mir nicht sicher, ob KW das gut findet (?), aber ich habe die B-Tree Remove Aufgabe gecrawlt, damit ich die einzelnen Fälle besser lernen kann:
https://davidgengenbach.de/aud/btree-remove/

Falls das nicht gewünscht ist, kann ichs direkt wieder runternehmen!
(Falls noch mehr Aufgaben gecrawlt werden sollen, kann ich das natürlich auch machen)

(Hier der Code dazu: https://github.com/davidgengenbach/nabl ... se-crawler)

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

Re: B-Tree Remove Unklarheit

Beitrag von luedecke » 19. Sep 2016 15:44

paprikawuerzung hat geschrieben:Ich bin mir nicht sicher, ob KW das gut findet (?), aber ich habe die B-Tree Remove Aufgabe gecrawlt, damit ich die einzelnen Fälle besser lernen kann:
https://davidgengenbach.de/aud/btree-remove/

Falls das nicht gewünscht ist, kann ichs direkt wieder runternehmen!
(Falls noch mehr Aufgaben gecrawlt werden sollen, kann ich das natürlich auch machen)

(Hier der Code dazu: https://github.com/davidgengenbach/nabl ... se-crawler)
Solange mir keiner das Logo zweckentfremdet, dürfen Inhalte aus Nabla so weit im Netz verteilt werden, wie es jedem beliebt :mrgreen:

Antworten

Zurück zu „AuD: Arbeit mit Nabla“