Wiki: „B-tree: shift key to sibling” unvollständig?

Symen
Erstie
Erstie
Beiträge: 19
Registriert: 5. Mai 2013 12:25

Wiki: „B-tree: shift key to sibling” unvollständig?

Beitrag von Symen »

Kann es sein, dass im genannten wiki in der Implementierung eine Zeile fehlt?

1. If shiftRight:

3. If i = n +1:
1. Set p.children[k].keys[1] := p.keys[k]
2. Set p.keys[k] := p.children[k-1].keys[p.children[k-1].n]
3. Increment p.children[k].n byone
4. Decrement p.children[j-1].n byone


Meiner Meinung nach müsste hier noch so etwas stehen wie:

Set p.children[k].children[0] := p.children[k-1].children[p.children.[k-1].n]


Zum Verständnis hatte ich versucht aus dem B-Tree in Übung 4|Aufgabe 3 den Wert 99 zu löschen.
(B-tree im Anhang)

Und hier muss ja als erstes die genannte Funktion aufgerufen werden, um die 75 vor die 95 zu schreiben und die 70 hoch in die Wurzel zu ziehen, wo die 75 ersetzt wird.
Den nächste Schritt konnte ich jetzt nicht im wiki nachvollziehen. Hier sollte dann noch das „leaf“ mit den Werten (71,72,) als erstes „child“ des Knoten (75,95,) geschrieben werden.

Falls die Implementierung im Wiki stimmt, wo findet dort dieser Schritt statt?


Gruß Simon
Dateianhänge
b-tree.png
b-tree.png (22.43 KiB) 487 mal betrachtet

R_Egert
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 180
Registriert: 8. Sep 2009 23:27

Re: Wiki: „B-tree: shift key to sibling” unvollständig?

Beitrag von R_Egert »

Heya,

Ja da sollte denke ich noch eine Zeile für das Umbiegen der Children rein.

Viele Grüße

Rolf
Tutor:
  • Einführung in Trusted Systems WS11/12, WS12/13, WS13/14, WS14/15
  • GDI II SS11, SS12, SS13, SS14
  • Einführung in die Kryptographie WS14/15

Antworten

Zurück zu „Archiv“