Nabla B-tree remove

Bei Postings zu Algorithmus X lassen Sie Ihren Betreff bitte mit
"X: " beginnen, bei allgemeinen Postings zu Nabla bitte mit "Nabla: ", jeweils gefolgt von einer möglichst präzisen Überschrift, danke!

Moderator: Algorithmen und Datenstrukturen

Forumsregeln
Bei Postings zu Algorithmus X lassen Sie Ihren Betreff bitte mit
"X: " beginnen, bei allgemeinen Postings zu Nabla bitte mit "Nabla: ", jeweils gefolgt von einer möglichst präzisen Überschrift, danke!
Hallo
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 162
Registriert: 22. Apr 2015 19:03

Nabla B-tree remove

Beitrag von Hallo » 19. Sep 2016 13:58

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
Windoof-User
Windoof-User
Beiträge: 25
Registriert: 14. Apr 2016 15:03

Re: Nabla B-tree remove

Beitrag von jr29zyni » 19. Sep 2016 14:37

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.

Benutzeravatar
luedecke
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 124
Registriert: 17. Mär 2015 00:08

Re: Nabla B-tree remove

Beitrag von luedecke » 19. Sep 2016 15:38

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.

Antworten

Zurück zu „AuD: Arbeit mit Nabla“