B-Tree insert Invariante Problem?

onbes
Mausschubser
Mausschubser
Beiträge: 98
Registriert: 30. Jul 2011 18:43

B-Tree insert Invariante Problem?

Beitrag von onbes »

Hey,

"Aus dem Wiki kennen sie die iterative Methode insert der Datenstruktur b-tree.
Betrachten Sie folgenden konkreten Input: Die Ordnung (M) des B-Tree ist 2.
Die Struktur des Baums und die enthaltenen Keys entsprechen den folgenden Werten in der angegebenen Einfügereihenfolge = 100,200,400,500,300,350,150,50.

Stellen sie den B-Baum in einer Skizze dar.

Fügen sie mit der insert Methode den Schlüssel 75 in den B-Tree ein und betrachten Sie speziell Iteration Nr. 1. Geben Sie die Variante und Invariante an und erläutern Sie, warum die Situation unmittelbar nach der Iteration Nr. 1 die Schleifeninvariante erfüllt und warum der Übergang vom Zustand unmittelbar vor Iteration Nr. 1 zum Zustand unmittelbar nach Iteration Nr. 1 die Schleifenvariante erfüllt."

Ich überlege gerade, wie ein B(inary)-Tree gegeben werden könnte.
Ist die Aufgabenstellung so wie ich sie formuliert habe ok? Falls nein, welche Möglichkeiten gibt es noch einen B-Baum als Text anzugeben? Oder gibt es ein Bild eines B(inary) Baums mit schon eingefügen Schlüsseln?

Andere Frage:
In dem obigen Beispiel ist es so, dass das "hoch propagieren" des entsprechenden Schlüssels des Knotens, in den eingefügt werden muss dazu führt (hat maximale Anzahl Elemente), dass der Elternknoten davon nun maximale Anzahl Schlüssel enthält. P steigt nach dem Split zwar ab und die Invariante ist nicht verletzt, aber man hat nun im Baum nen Knoten, der voll ist.

Um den vollen (weiter oben liegenden) Knoten kümmert sich dann die nächste Operation, nach meinem insert der 75, hab ich das richtig verstanden?

Danke

Zurück zu „Archiv“