Seite 1 von 1

Nabla B-tree remove

Verfasst: 19. Sep 2016 13:58
von Hallo
Hi,
Warum wird die 73, die an der Höhe h=2 gelöscht, und nicht die an der Wurzel ?

Screenshot auf Dropbox.
https://www.dropbox.com/s/zod3d2rnqgchb ... 6.png?dl=0

Re: Nabla B-tree remove

Verfasst: 19. Sep 2016 14:37
von jr29zyni
Sobald du ein Vorkommen deines Wertes gefunden hast, gehst du einmal nach links und dann so weit wie möglich nach rechts und ersetzt das Vorkommen durch den Wert ganz rechts.

Re: Nabla B-tree remove

Verfasst: 19. Sep 2016 15:38
von luedecke
jr29zyni hat geschrieben:Sobald du ein Vorkommen deines Wertes gefunden hast, gehst du einmal nach links und dann so weit wie möglich nach rechts und ersetzt das Vorkommen durch den Wert ganz rechts.
Das ist kein Binary search tree!
Hallo hat geschrieben:Hi,
Warum wird die 73, die an der Höhe h=2 gelöscht, und nicht die an der Wurzel ?

Screenshot auf Dropbox.
https://www.dropbox.com/s/zod3d2rnqgchb ... 6.png?dl=0
Pointer steht auf der 73:h=2, darf diese aber nicht löschen, rotiert diese nach rechts ins Blatt, sodass die 65:h=2 nun an der Stelle des Pointers steht und im rechten Kind die Sequenz [73,73,80]:h=3 steht. Pointer wandert herunter und der erste Treffer und gleichzeitig der Kandidat zum Löschen ist die 73, die ursprünglich auf h=2 war.

Der Löschalgorithmus vom B-tree ist diesbezüglich als greedy zu betrachten. Er löscht den Wert, den er zuerst antrifft, insofern alle Prämissen erfüllt sind.
Es gibt auch Fälle, in welchen der Algorithmus z.B. auf eine 73 trifft und die Löschprämissen nicht erfüllt sind. Demnach wird eine Umstrukturierung vorgenommen und es dennoch eine andere 73 löscht.