B-tree: shift key to sibling - Fehler?

Flix1337
Erstie
Erstie
Beiträge: 12
Registriert: 27. Apr 2013 18:22

B-tree: shift key to sibling - Fehler?

Beitrag von Flix1337 »

Hi,

ich habe vll einen Fehler gefunden. In Schritt 2.1 des Induction Steps wird mit der Zählvariable i gearbeitet. Da diese nirgends explizit gesetzt wird und in der Invariante i >= 0 verwendet wird, gehe ich davon aus dass sie bei 0 anfängt. Wenn nun in Schritt 2.1 das Feld p.children[k].keys angesprochen werden soll kann dies doch gar nicht möglich sein, da keys erst bei 1 anfängt.
Verstehe ich das nur falsch oder ist da tatsächlich ein Fehler?

Grüße

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

Re: B-tree: shift key to sibling - Fehler?

Beitrag von JannikV »

Hallo,

in den Algorithmen im Wiki ist in der i-ten Iteration i = i. Also in der ersten Iteration ist i = 1.

In der Invariante ist von i >= 0 die Rede weil die Invariante auch vor der ersten Iteration gilt.

VG

Antworten

Zurück zu „Archiv“