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
Nabla B-tree remove
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!
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!
Re: Nabla B-tree remove
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
Das ist kein Binary search tree!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.
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.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
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.