Ü9: Fehler im Wiki? - B-tree:remove - "move key to sibling"?

tmuecksch
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 123
Registriert: 19. Apr 2013 10:51

Ü9: Fehler im Wiki? - B-tree:remove - "move key to sibling"?

Beitrag von tmuecksch »

Hallo,

In der Induktionsbasis des remove-Algorithmus auf B-Tree, wird unter 4.2.1.1 und 4.2.2.1 die Methode "B-tree: move key to sibling" aufgerufen. Diese ist jedoch im B-Tree Eintrag gar nicht definiert. Ist damit "shift key to sibling" gemeint? :shock:

Direkt-Links:
B-Tree
http://wiki.algo.informatik.tu-darmstad ... php/B-tree
B-Tree: remove
http://wiki.algo.informatik.tu-darmstad ... ee:_remove


Vielen Dank im Voraus :!:

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

Re: Ü9: Fehler im Wiki? - B-tree:remove - "move key to sibli

Beitrag von JannikV »

Ja, das hatte ich vorhin schon korrigiert.

tmuecksch
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 123
Registriert: 19. Apr 2013 10:51

Re: Ü9: Fehler im Wiki? - B-tree:remove - "move key to sibli

Beitrag von tmuecksch »

Mir ist da noch etwas aufgefallen in B-Tree in der Methode "shift key to sibling".
Unter Postcondition unter 1.3 ist von p.children[k-1].children[n] die Rede.
Und unter Postcondition unter 2.2 ist von p.children[k-1].children[n-1] die Rede.

Wo kommt das n her?

[Edit: habe noch so einen Fall gefunden und hinzugefügt]

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

Re: Ü9: Fehler im Wiki? - B-tree:remove - "move key to sibli

Beitrag von JannikV »

Hey,

gut aufgepasst. Ich habe es jetzt durch p.children[k-1].n ersetzt.

VG

tmuecksch
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 123
Registriert: 19. Apr 2013 10:51

Re: Ü9: Fehler im Wiki? - B-tree:remove - "move key to sibli

Beitrag von tmuecksch »

Müsste es aber nicht bei 2.2 der Methode "shift key to sibling" lauten:

p.children[k-1].children[p.children[k-1].n] STATT p.children[k-1].children[p.children[k-1].n+1]

Den so würde wenn angenommen 3 keys belegt wären der Pointer 4 gesetzt, was aber logisch inkonsistent ist, da an Stelle 4 kein key hinterlegt wäre.

EDIT:
Frage geklärt:
Es ist korrekt weil p.children[k-1].n im vorherigen Verlauf nicht erhöht wird; wenn auch logisch inkonsistent da B-tree-Node.n so definiert ist, dass n die Anzahl von gesetzten Keys im Knoten angibt und der Zustand des Knotens dann nicht mit n übereinstimmt...

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

Re: Ü9: Fehler im Wiki? - B-tree:remove - "move key to sibli

Beitrag von JannikV »

Das ist nicht logisch inkonsistent. Die Implementationsinvariante, also dass n die Anzahl von Keys angibt gilt vor und nach jedem Methodenaufruf. Mitten in einem Methodenaufruf lässt sich das gar nicht sicher stellen.
Wie auch. Angenommen ich will einen Key entfernen. Im einfachsten Fall wären dazu zwei Schritte nötig.
((5, 10, ), 2) --entferne(10)--> ((5, , ), 2) --verringere(n)--> ((5, , ), 1)
Dazwischen ist es natürlich nicht konsistent, weil die Methode noch nicht fertig ist.

VG

Antworten

Zurück zu „Archiv“