Seite 1 von 1

B-tree Remove 3. Invariante

Verfasst: 3. Sep 2012 10:10
von ut53xuco
Hi,

Ich verstehe die dritte Invariante von B-tree remove nicht ganz, Zitat:
3. It is found=true if, and only if, K is contained at least once in one of the current nodes of previous iterations.
Ich würde es so übersetzen:

Es gilt found=true wenn, und nur dann wenn, K mindestens ein Mal in einem der aktuellen Knoten der vorherigen Iterationen vorkommt.

Das ergibt für mich aber keinen Sinn... heißt das jetzt bevor ich found=true setzten kann muss das Element, das ich suche bereits ein mal in einer höheren Ebene im Baum vorhanden gewesen sein, aber nur in Knoten durch die ich gelaufen bin? Dann wäre ich ja quasi schon ein mal über meinen Key Iteriert und mache erst beim 2. Mal halt?
Ich weiß wie remove funktioniert (denke ich) aber das hier verstehe ich noch nicht ganz... :(

Vielen Dank für Eure Hilfe

Re: B-tree Remove 3. Invariante

Verfasst: 3. Sep 2012 10:22
von John_Silver
Schau dir mal den Implementation von Induction Step Nr. 2.1 an. Das heißt wir befinden uns gerade mitten im Baum. Der Knoten auf den p zeigt ist also KEIN Blatt. Wenn jetzt der Schlüßel K in diesem Knoten gefunden wurde, wird found auf true und der Pointer p' auf diesen Knoten gesetzt.
Mit anderen Worten der Algorithmus löscht immer den am tiefsten vorkommenden angegebenen Schlüßel.

Re: B-tree Remove 3. Invariante

Verfasst: 3. Sep 2012 10:36
von ut53xuco
Danke, der Induction Step hilft ein bisschen weiter.
Wie ich die Inavriante interpretiert habe, wird aber erst dann found=true gesetzt wenn ich bereits zum zweiten Mal K gefunden habe. Das ist nicht der Fall, oder? (wegen "vorherigen Iterationen")
Der Rest ist mir klar, der Algorithmus terminiert im Blatt und überschreibt dann entsprechend K.

Re: B-tree Remove 3. Invariante

Verfasst: 3. Sep 2012 10:48
von John_Silver
So wie ich die Invariante verstehe (so steht sie dann auch in der Implementation): Wenn K wenigstens ein Mal im currentPath auftaucht, so ist found=true. Sobald wir K auf unserem Weg begegnen ist die Variable true. :)

Re: B-tree Remove 3. Invariante

Verfasst: 3. Sep 2012 11:05
von ut53xuco
Dann ergibt alles wieder Sinn wenn man es so interpretiert :wink: