H9.1 !! FEHLER in WIKI !! B Tree Remove IS 2.1

ic89dixy
Erstie
Erstie
Beiträge: 12
Registriert: 15. Okt 2012 18:07

H9.1 !! FEHLER in WIKI !! B Tree Remove IS 2.1

Beitrag von ic89dixy »

Da ist ein Fehler in dem WIKI. B-Tree Remove Punkt 2.1

Nehmen wir an
1. der Key K befindet sich im Node p an pos k = 1
2. p ist kein Leaf
3. p hat M - 1 Elemente
4. p.child[0] hat M - 1 Elemente unc p.child[1] hat mehr als M - 1 Elemente

Jetzt passiert folgendes im Induktionsschritt:
2. Ich erreiche den Node p
2.1.1 - 2.1.2 K ist in p enthalten also wird found = true gesetzt und p' = p als Referenz für den gefundenen Node

Danach wird Punkt 2.3.2.2 aufgerufen und die Keys werden links rotiert sodass K jetzt in p.child[0].keys[n+1] liegt und nicht mehr in p.

Damit ist die Invariante in Punkt 3 und 4 verletzt
weil die Markierung p' jetzt nicht mehr auf eine Node zeigt die den Key enthällt
und found = true ist ebenfalls nicht korrekt da der Key nicht mehr in dem durchgelaufenen Pfad liegt.

Vorschlag:
Man sollte den Punkt 2.1 erst nach dem rotieren oder mergen aufrufen und zwar in Punkt 2.4

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: H9.1 !! FEHLER in WIKI !! B Tree Remove IS 2.1

Beitrag von JannikV »

Hallo,

es ist sehr schwer nachzuvollziehen ob du da tatsächlich Recht hast. Problem ist, dass du dir nicht einfach irgendeinen Baum zusammenschreiben kannst. Der Baum muss aus einer Folge von Methodenaufrufen entstanden sein. Also im Wesentlichen eine Menge inserts. Dann ist es möglich, dass das von dir gewählte Beispiel sonst gar nicht entstehen kann.

Meine Bitte: könntest du ein konkretes Beispiel machen, angefangen vom Aufbauen des Baumes mit insert, s.d. dieser Fehler demonstriert wird? Dann können wir von unserer Seite besser überprüfen ob das seine Richtigkeit hat.

VG


PS: Wenn du tatsächlich Recht hast, kannst du dir in meiner Sprechstunde ein Snickers abholen kommen :D

robertH
Mausschubser
Mausschubser
Beiträge: 58
Registriert: 29. Apr 2013 13:11

Re: H9.1 !! FEHLER in WIKI !! B Tree Remove IS 2.1

Beitrag von robertH »

Hallo ic89dixy,

Ich bin mir nicht ganz sicher ob das Wiki fehlerhaft ist oder nicht, aber ich habe mal ein Beispiel konstruiert:

Erst einmal kann deine Voraussetzung 3 nicht eintreten, da nach der Invariante immer mindestens M keys im Knoten p sein muss.
Aber nehmen wir mal an, dass es M sind und zwar beim B-tree der Hausaufgabe zeigt p auf den Knoten (29, 40, ) mit den Nachfolgern (20, , ) und (32, 35, ) und wir wollen K = 29 löschen. In diesem Fall sind deine anderen Voraussetzungen erfüllt und es käme im Schritt 2.3.2.2 zur links Rotation dann hätten wir (32, 40, ) mit den Nachfolgern (20, 29, ) und (35, , ), falls ich jetzt nichts falsch gemacht habe. Da wir immer noch die 29 löschen wollen, setzen wir p auf children[0] am Ende.

Die Frage ob das Wiki nun korrekt ist oder nicht, hängt meines Erachtens nun daran ob p' nun auf die neue Adresse von p zeigt oder immer noch an die alte. Zeigt es auf die neue, ist es korrekt, dass K sich in p' befindet, da es nun children[0] ist. Ist es noch die Alte, ist das Wiki wie von dir herausgestellt, falsch.

ic89dixy
Erstie
Erstie
Beiträge: 12
Registriert: 15. Okt 2012 18:07

Re: H9.1 !! FEHLER in WIKI !! B Tree Remove IS 2.1

Beitrag von ic89dixy »

Ist ziemlich genau das Beispiel an dem ich das gemerkt habe. (Mit der 29)

Zu p' wird auf p gesetzt.
Dies geschieht nicht. Ich hab extra danach gesucht.
Und das verletzt in diesem Fall die Invariante da K nach dem Setzen von p' aus p' entfernt wird.

!!! Da dies nicht korrigiert wird ist die Implementierung falsch. !!!

Wenn p' immer auf p zeigt (Das heißt automatisch mitwandert) zeigt ergibt der Zeiger p', keinen Sinn
Und da p = p.child[0] ja die Variante und der Sprung in die nächste Rekursion ist sollte das auch nicht mitwandern.

Dieser Fehler im Wiki ist ziemlich offensichtlich.

Der Fehler liegt einfach daran, dass das setzen von p' zu früh gemacht wird. (in Punkt 2.1)
Wenn es nach dem rotieren (So bei 2.4) geschieht wird es korrekt.
Oder man kann es nachträglich richtig frickeln, was ziemlich unschön wäre und nicht angemessen für das Wiki

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: H9.1 !! FEHLER in WIKI !! B Tree Remove IS 2.1

Beitrag von JannikV »

Gut, ich habe jetzt auch mal das Beispiel remove(29) mit dem Übungsblatt-Baum gemacht und du hast recht, dass die Invariante verletzt wird. Ich habe aus Punkt 2.1 jetzt Punkt 2.3 gemacht. Das Problem sollte damit behoben sein.

VG

Antworten

Zurück zu „Archiv“