Frage zu B-Tree: delete

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

Frage zu B-Tree: delete

Beitrag von NonStop »

Ich habe eine Aufgabenstellung bekommen und eine Lösung eingegeben wie auf folgendem Bild:
Bild

Die korrekte Lösung sah so aus:
Bild

Meine Frage ist, wieso man zuerst merge an der Wurzel machen soll, wenn die zu löschende Zahl sich in einem Blatt befindet und die Ordnung des Baumes nach einfachem Löschen erhalten bleibt?

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

Re: Frage zu B-Tree: delete

Beitrag von steffen12 »

Meine Frage ist, wieso man zuerst merge an der Wurzel machen soll, wenn die zu löschende Zahl sich in einem Blatt befindet und die Ordnung des Baumes nach einfachem Löschen erhalten bleibt?
Das Wiki gibt Aufschluss: Invariante von B-tree : remove (5.).
http://wiki.algo.informatik.tu-darmstad ... ee:_remove

Die Invariante des Algorithmus fordert, dass der aktuelle Knoten (auf den der Zeiger p zeigt) immer mindestens M Schlüssel enthält (außer es handelt sich um die Wurzel), weil andernfalls in diesem Knoten kein Schlüssel gelöscht werden könnte, ohne die B-Baum-Eigenschaften zu zerstören.
Wenn die Voraussetzungen für einen Merge an der Wurzel erfüllt sind (so wie in deinem Beispiel) dann kann der Zeiger p aufgrund der Invariante weder links noch rechts hinabsteigen. Daher ist die Maßnahme erforderlich.

Grüße, Steffen

KaeferZuechter
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 108
Registriert: 15. Apr 2015 19:24

Re: Frage zu B-Tree: delete

Beitrag von KaeferZuechter »

Der Algowiki-Algorithmus verfolgt eine Single-Pass-Strategie.
Daher muss jeder Knoten mit Minimalzahl Schlüssel garantieren, dass er seine Invarianten auch nach Löschen eines Kindes noch erfüllt.
Also merged man, sobald er seine Minimalzahl erreicht. Im allgemeinen Fall also n = M - 1, an der Wurzel eben bei n = 1 und Kindern mit n = M - 1.


Wenn man das nicht machen würde, müsste man eine Strategie verfolgen, die nach dem Löschen alle Invarianten baum-aufwärts korrigiert.
Das ist möglich, allerdings nicht unbedingt einfacher.
IT'S CALLED A FOURIER TRANSFORM WHEN YOU TAKE A NUMBER AND CONVERT IT TO THE BASE SYSTEM WHERE IT WILL HAVE MORE FOURS, THUS MAKING IT "FOURIER". IF YOU PICK THE BASE WHERE IS HAS THE MOST FOURS, THE NUMBER IS SAID TO BE "FOURIEST".

\(1160_8 \rightarrow 624_{10} \rightarrow 440_{12} \rightarrow 4444_5\)

- Zach Weiner -

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Frage zu B-Tree: delete

Beitrag von Prof. Karsten Weihe »

KaeferZuechter hat geschrieben: Wenn man das nicht machen würde, müsste man eine Strategie verfolgen, die nach dem Löschen alle Invarianten baum-aufwärts korrigiert.
Das ist möglich, allerdings nicht unbedingt einfacher.
Stimme zu.

Ich hatte mich aus didaktischen Gründen gegen die nachträgliche Korrektur baum-aufwärts und für die prophylaktische Korrektur schon beim Abstieg entschieden - B-Bäume sind auch so schon ein ausreichend schwieriges Thema, muss man nicht noch verkomplizieren. :shock:

KW

Antworten

Zurück zu „Archiv“