B-Tree remove - Frage zur Impl. des I.S. 1.2.2

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

B-Tree remove - Frage zur Impl. des I.S. 1.2.2

Beitrag von tmuecksch »

Hallo,

in der Implementierung des Induktionsschritts unter 1.2.2 heißt es: "Set p'.keys[k]:=p.keys[p.n]". Was bedeuten würde das der größte Wert des Knotens p mit dem zu ersetzenden Wert im Knoten darüber überschrieben wird.

Das bricht aber doch die Bedingungen des B-Baums sofern p das rechteste Kind von p' und und p' = p.children[k] (also rechtes Kind von K) ist, da dann die Werte im Kind Knoten kleiner sind als der Wert p'.keys[k].

Oder liege ich da falsch?

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

Re: B-Tree remove - Frage zur Impl. des I.S. 1.2.2

Beitrag von tmuecksch »

Zusätzlich habe ich im Schritt vorher das Problem (was vielleicht zu dem oben genannten Problem geführt hat), dass wenn ich Beispielsweise die 70 (also K=70) aus unserem Beispielbaum in Ü9 löschen möchte, ich an den Punkt komme, dass p auf den "70"- enthaltenen Knoten zeigt also [68|70|__] und dann in 2.2 ein k wählen soll, sodass gilt: k in {1, ..., p.n} und K > p.keys[k]. Dieses k kann ich aber nicht wählen, da wir hier > und nicht >= stehen haben.

Wie soll ich da weiter machen?

robertH
Mausschubser
Mausschubser
Beiträge: 58
Registriert: 29. Apr 2013 13:11

Re: B-Tree remove - Frage zur Impl. des I.S. 1.2.2

Beitrag von robertH »

Die keys sind ja von 1 bis n nummeriert und da K = 70 > 68 = p.keys[1] gilt, ist dein k die 1. Dementsprechend musst du also in p.children[1] absteigen um den direkten Vorgänger der 70 zu finden bzw. die 70 selbst, falls sie dort hin rotiert wird.

Ansonsten schreibst du
"Set p'.keys[k]:=p.keys[p.n]". Was bedeuten würde das der größte Wert des Knotens p mit dem zu ersetzenden Wert im Knoten darüber überschrieben wird.
. Hierbei verwechselst du was ersetzt wird. Ersetzt wird p'.keys[k] und zwar durch p.keys[p.n].

Benutzeravatar
ob1
Windoof-User
Windoof-User
Beiträge: 37
Registriert: 10. Dez 2012 14:30

Re: B-Tree remove - Frage zur Impl. des I.S. 1.2.2

Beitrag von ob1 »

Zum ersten Teil: Laut Invariante zeigt p auf den Bereich des "immediate predecessor"s, also auf den nächst-kleineren Kindknoten von p'. Wenn du dir davon den größten Wert anschaust, dann ist das genau der nächst-kleinere Wert unter K. Alle anderen Werte von p sind kleiner als eben dieses p[n].

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

Re: B-Tree remove - Frage zur Impl. des I.S. 1.2.2

Beitrag von tmuecksch »

Vielen vielen Dank. Da stand ich auf dem Schlauch...
Das kommt davon wenn man stundenlang nichts anderes sieht -.-

Antworten

Zurück zu „Archiv“