B-tree Remove 3. Invariante

[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

[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.

[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.

[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.

[ut53xuco]

Dann ergibt alles wieder Sinn wenn man es so interpretiert