B-tree Remove 3. Invariante

Benutzeravatar
ut53xuco
Mausschubser
Mausschubser
Beiträge: 57
Registriert: 20. Nov 2011 18:07

B-tree Remove 3. Invariante

Beitrag 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

John_Silver
Windoof-User
Windoof-User
Beiträge: 41
Registriert: 18. Okt 2009 23:27

Re: B-tree Remove 3. Invariante

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

Benutzeravatar
ut53xuco
Mausschubser
Mausschubser
Beiträge: 57
Registriert: 20. Nov 2011 18:07

Re: B-tree Remove 3. Invariante

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

John_Silver
Windoof-User
Windoof-User
Beiträge: 41
Registriert: 18. Okt 2009 23:27

Re: B-tree Remove 3. Invariante

Beitrag 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. :)

Benutzeravatar
ut53xuco
Mausschubser
Mausschubser
Beiträge: 57
Registriert: 20. Nov 2011 18:07

Re: B-tree Remove 3. Invariante

Beitrag von ut53xuco »

Dann ergibt alles wieder Sinn wenn man es so interpretiert :wink:

Antworten

Zurück zu „Archiv“