Nabla B-tree remove

[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

[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.

[luedecke]

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!

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.