Einführung in den Löschvorgang von B-Tree

Im vorherigen Artikel https://www.jb51.net/article/154157.htm haben wir den Einfügevorgang von B-Tree vorgestellt. In diesem Artikel werden wir den Löschvorgang von B-Tree vorstellen.

Beim Löschen eines Knotens in einem B-Baum kann dieser Elemente von Geschwisterknoten übernehmen, Elemente mit untergeordneten Knoten austauschen oder sogar Knoten zusammenführen.

Als Grundlage für die Löschung verwenden wir folgenden Baum.

Lassen Sie uns zunächst die Definition dieses Baums klären. Es handelt sich um einen Baum 5. Ordnung. Daher beträgt die Anzahl der Elemente in jedem Knoten 2 bis 4.

Wir löschen nacheinander die vier Elemente 8, 16, 15 und 4.

Löschen Sie zuerst 8, da durch das Löschen von 8 die Eigenschaften des Baums nicht zerstört werden und Sie diese daher direkt löschen können. Erhalten Sie Folgendes

Anschließend wird 16 gelöscht, wodurch nur noch ein 13-Knoten übrig bleibt, der die Anforderung, dass die Anzahl der Elemente im Knoten 2 bis 4 beträgt, nicht erfüllt. Es sind also Anpassungen erforderlich. Hier können Sie Knoten vom Kind übernehmen und 17 erhöhen, um das folgende Bild zu erhalten. Es ist hier nicht möglich, Knoten von Geschwisterknoten auszuleihen, da nach dem Ausleihen von 6 von Knoten 3 und 6 die verbleibenden 3 die Anforderung nicht erfüllen würden. Zudem ist es nicht möglich, 15 der Kinder zu versetzen, da dies zur Folge hätte, dass die restlichen 14 die Voraussetzungen nicht erfüllen.

Löschen Sie dann 15. Nach dem Löschen von 15 ist die gleiche Anpassung erforderlich. Die Anpassungsmethode besteht darin, 18 zu erhöhen und 17 auf die ursprüngliche Position von 15 zu verringern, und wir erhalten das folgende Bild.

Anschließend löscht man Element 4. Nach dem Löschen von 4 bleibt nur noch 5 im Knoten übrig, welches angepasst werden muss. Keiner der Geschwisterknoten verfügt jedoch über zusätzliche Knoten, die ausgeliehen werden können. Daher ist eine Knotenzusammenführung erforderlich. Es gibt viele Möglichkeiten, Knoten zusammenzuführen, und wir können eine davon auswählen. Hier wählen wir 3 im übergeordneten Knoten aus, um ihn zu senken, und führen ihn mit 1, 2 und 5 zusammen, wie in der folgenden Abbildung gezeigt.

Diese Anpassung führte jedoch dazu, dass 6 die Anforderungen nicht mehr erfüllte. Darüber hinaus erfüllen 6 Nicht-Wurzelknoten, aber nur 2 untergeordnete Knoten die Anforderungen ebenfalls nicht. Muss weiter angepasst werden. Die Anpassungsmethode besteht darin, 10 zu versenken und mit 6, 13 und 18 zum Stammknoten zusammenzuführen, wie in der folgenden Abbildung dargestellt.

Beenden.

Zusammenfassen

Das Obige ist der vollständige Inhalt dieses Artikels. Ich hoffe, dass der Inhalt dieses Artikels einen gewissen Lernwert für Ihr Studium oder Ihre Arbeit hat. Vielen Dank für Ihre Unterstützung von 123WORDPRESS.COM. Wenn Sie mehr darüber erfahren möchten, schauen Sie sich bitte die folgenden Links an