B-Baum Delete Fall 3b)

Benutzeravatar
^Lara^
Mausschubser
Mausschubser
Beiträge: 68
Registriert: 17. Jan 2005 12:57

B-Baum Delete Fall 3b)

Beitrag von ^Lara^ »

Wir versuchen gerade das Löschen im B-Baum zu verstehen.
Doch Fall 3b) ist uns noch garnicht klar.

Im Script http://www.iua.upf.es/~rramirez/TA/btrees.pdf auf seite 26 ist ein Bsp.

Wieso kann nicht einfach die "4" gelöscht werden? Warum muss man die beiden Geschwister "2,12" und "20,23" mit der Wurzel "16" vereinigen?
Eine andere Frage ist auch warum kann die "4" nicht gefunden werden? "Recursion cannot descend to node 3, 12 because it has t−1 keys." Wieso?

Im Buchmann Script heißt es auch: (Allgemein bei Fall 3)
Ist k nicht x,...

kann uns das einer erklären?

Vielen vielen Dank!!

Benutzeravatar
Maeher
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 282
Registriert: 14. Okt 2007 23:02
Kontaktdaten:

Re: B-Baum Delete Fall 3b)

Beitrag von Maeher »

Der delete Algorithmus stellt beim absteigen sicher, dass jeder durchsuchte Knoten immer mindestens t Elemente hat (man also einfach löschen kann) Dadurch verhindert man, beim löschen was kaputt zu machen und nachher wieder reparieren zu müssen.
Es wird also vor dem Absteigen geprüft, ob genug Elemente im Kind vorhanden sind, und wenn dem nicht so ist, sorgt man dafür, dass es so ist.

Benutzeravatar
Krümelmonster
Geek
Geek
Beiträge: 767
Registriert: 17. Okt 2007 13:58
Wohnort: Jossgrund

Re: B-Baum Delete Fall 3b)

Beitrag von Krümelmonster »

Die Frage ist nur, ob auch beim Suchen des Nachfolgers oder Vorgängers die B-Baum-Eigenschaft geprüft wird.
Stell deinen Fuß auf einen hohen Sockel
Mach dir ein Haar aus tausend Locken
Du bleibst doch immer, was du bist!

Antworten

Zurück zu „Archiv“