Wie funktioniert der Algorithmus B-Tree: remove WIRKLICH?

LukasPhysiker
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 111
Registriert: 6. Mai 2017 13:05

Wie funktioniert der Algorithmus B-Tree: remove WIRKLICH?

Beitrag von LukasPhysiker » 9. Sep 2017 21:21

Wenn man sich im Video aus der Videothek ansieht, wie das Löschen eines Eintrags aus einem B-Baum funktioniert, wird z.B. beschrieben, dass ein Element einfach gelöscht werden kann, wenn es sich auf einem Blatt befindet, das genug Einträge hat:
https://www.youtube.com/watch?v=vbRZ8h6ROYc&t=681s

Wenn man aber die Aufgabe im Nabla macht, dann stellt man durch Reverse Engineering der Musterlösungen der generierten Aufgaben aber fest, dass z.B. immer am Anfang die Wurzel mit ihren Kindknoten gemergt werden soll. Mittlerweile mache ich das schon bevor ich mir überhaupt ansehe, welches Element überhaupt entfernt werden soll. Da diese Aufgabe in beiden Altklausuren eine Klausuraufgabe war, versuche ich gerade, mich nochmal in diese Aufgabe einzuarbeiten und stelle immer wieder fest, dass es einen Fall gibt, den ich vorher nicht hatte und lerne so nur langsam durch Trial & Error.

Daher: Wie sieht dieser Algorithmus wirklich aus? Ich suche nach einer Quelle, die man Schritt für Schritt durchgehen könnte um so garantiert die richtige Antwort für jeden Baum, den Nabla einen vorsetzt, finden zu können. Das Video scheint mir dazu ja recht nutzlos zu sein, bzw. sogar Falschinformationen zu liefern.

Benutzeravatar
LordMaddhi
Nichts ist wie es scheint
Beiträge: 23
Registriert: 20. Apr 2017 11:57
Wohnort: Darmstadt, Hessen

Re: Wie funktioniert der Algorithmus B-Tree: remove WIRKLICH?

Beitrag von LordMaddhi » 24. Sep 2017 12:41

Schließe mich dem Kommentar an. :roll:
Ich bin nicht die Signatur. Ich putze hier nur.

Mel
Neuling
Neuling
Beiträge: 6
Registriert: 23. Apr 2017 20:29

Re: Wie funktioniert der Algorithmus B-Tree: remove WIRKLICH?

Beitrag von Mel » 24. Sep 2017 13:25

Schließe mich auch an, würde mich vor allem interessieren, ob man in der Klausur Punkte bekommt wenn man es macht wie im video.

kommiker
Mausschubser
Mausschubser
Beiträge: 51
Registriert: 24. Apr 2017 19:25

Re: Wie funktioniert der Algorithmus B-Tree: remove WIRKLICH?

Beitrag von kommiker » 24. Sep 2017 14:03

Studentenanwort (keine Garantie auf Richtigkeit):

Zu Remove:
Man muss dort die Invariante beachten (ich glaube das wird auch so im Video gesagt), das wenn der Zeiger auf einen Knoten herabsteigen soll, dann darf dieser nicht minimale Anzahl Keys haben (so oder so ähnlich wird das auch im Video gesagt). Deshalb musst du, bei dem Fall der prakitsch zu 90% immer geben ist, nähmlich das die Wurzel genau einen Key hat und zwei Kinder mit auch genau einem Key, auch eine merge Operation machen. Weil du eben nicht zu einem der beiden Kindknoten herabsteigen kannst, weil die Invariante nicht geben ist.


Zu Insert:
So ähnlich ist es auch beim Insert. Beim insert ist die Invariante, dass du nicht zu eine Knoten herabsteigen darfst, welcher maximale Anzahl Keys hat (so oder so ähnlich auch im Video erklärt). Deshalb wenn du beim Insert auf einen Knoten herabsteigen willst, welcher maximale Anzahl keys hat, musst du eine Split- Operation machen, weil sonst nicht die Invariante erfüllt wäre.


Für bei Algorithmen gibt es also bestimmte Szenarien, wie man die Erfüllung der Invariante garantieren kann (durch umbauen des Baums) und auch muss. Diese habe ich mir anhand der durch Nabla generierten Lösungen einfach selbst hergeleitet.
Hoffe ich konnte weiterhelfen.

lg kommiker

Benutzeravatar
LordMaddhi
Nichts ist wie es scheint
Beiträge: 23
Registriert: 20. Apr 2017 11:57
Wohnort: Darmstadt, Hessen

Re: Wie funktioniert der Algorithmus B-Tree: remove WIRKLICH?

Beitrag von LordMaddhi » 25. Sep 2017 12:28

Das klingt einleuchtend... dankeschön :)
Ich bin nicht die Signatur. Ich putze hier nur.

LukasPhysiker
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 111
Registriert: 6. Mai 2017 13:05

Re: Wie funktioniert der Algorithmus B-Tree: remove WIRKLICH?

Beitrag von LukasPhysiker » 25. Sep 2017 21:50

Danke für deine Antwort, kommiker! So in der Art habe ich mir das ja auch überlegt, aber das Problem sind ja die Details. Es gibt immer wieder Situationen, in denen es nicht eindeutig ist, was man machen muss, da man z.B. entweder mit dem linken oder dem rechten Nachbarknoten mergen kann. Oder man kann mit dem einen Knoten mergen oder mit dem anderen einen Key shiften. Was genau man macht, ist, so wie ich das sehe, egal und von der Implementierung abhängig, aber hier haben wir eine bestimmte Implementierung, wo bei solchen Sachen immer eine ganz bestimmte dieser Optionen durchgeführt werden muss und diese Datails reverse engineeren zu müssen, kann man einem doch nicht zumuten!

Ich will es hier nochmal deutlich sagen: Selbst wenn jemand sonst immer diese Aufgabe bestanden hat, kann es immer noch sein, dass es eine Zweideutigkeit gibt, die diese Person noch nie durch die zufällige Auswahl des Baumes zu Gesicht bekommen hat. Das kann auch dich betreffen, der das hier gerade liest.

Können wir bitte eine offizielle Antwort auf diese Frage bekommen?

kommiker
Mausschubser
Mausschubser
Beiträge: 51
Registriert: 24. Apr 2017 19:25

Re: Wie funktioniert der Algorithmus B-Tree: remove WIRKLICH?

Beitrag von kommiker » 25. Sep 2017 23:46

Was mir auch geholfen hat diesen Remove-Algorithmus zu verstehen war die Vorlesungsaufzeichnung 15. Dort werden alle möglichen Fälle welche auftreten können und wie man im konkreten Fall die Invariante herstellen kann erklärt.

Wer noch Probleme mit Insert hat sollte sich Vorlesungsaufzeichnung 14 anschauen.


lg kommiker

lewo
Neuling
Neuling
Beiträge: 1
Registriert: 26. Sep 2017 13:02

Re: Wie funktioniert der Algorithmus B-Tree: remove WIRKLICH?

Beitrag von lewo » 26. Sep 2017 13:07

Dieses Problem hat mich auch die letzten Tage beschäftigt und die Antwort ist im Algowiki zu finden.
https://wiki.algo.informatik.tu-darmsta ... ee:_remove

Unter Induction Step, Implementation, 2. lässt sich heraus lesen, dass erst geprüft wird, ob kein rechter Nachbarknoten existiert, dann merge oder rotate mit dem linken.
Andernfalls, wenn ein rechter Nachbar existiert, merge oder rotate mit diesem rechten Knoten.

Kurz: Gibt es einen rechten Nachbarn, so wird mit diesem gearbeitet (entsprechend rotate oder merge), gibt es keinen, wird der linke genutzt.

Antworten

Zurück zu „Archiv“