H 8.4

[linn]

In H 8.4 gehts ja ganz allgemein um nen Mehrwegbaum.
Es muss also nicht rotiert bzw balanciert werden und die Knoten müssen keinen Mindestgrad haben?
Was muss beim Einfügen beachtet werden?
Muss ich zuerst versuchen die schlüssel in einem bereits vorhandenen Knoten einzufügen, oder könnte ich auch für jeden einen neuen Knoten erstellen (h=n).

Und wie ist das mim Löschen?
Das wird im Skript ja nur für B-Bäume und binäre Bäume beschrieben.

Also ich hab z.B. die Wurzel:
p0|K1|p1|K2|p3|K3|p4

und möchte K2 löschen.
jetzt gäbe es ja mehrere Möglichkeiten:
a) Die Knoten auf die p1 und p3 zeigen haben zusammen einen Ausgangsgrad <=m.
- dann könnte man sie ja einfach zu einem Knoten zusammenfassen und hätte immernoch den m-Baum.

b) p1 und p3 haben zusammen einen Ausgangsgrad >m
- dann könnte man den grössten linken Nachfahre löschen und mit ihm K2 überschreiben
- oder den kleinsten rechten

Mit welcher Strategie sollen wir die entstandenen Lücke ausfüllen?

[ivoch]

Ja, du musst nichts balancieren. Und du solltest schon die vorhandenen Knoten ausfühlen - entartete Mehrwegbäume sind zwar natürlich nach Definition "legal", aber doch unerwünscht, denn dann gehen ja deren Vorteile verloren.

Beim Löschen musst du beachten, dass es keine "Lücke" entsteht. Deine b) Idee sieht schon mal nicht schlecht aus.

[Niggi]

wenn du meinst knoten auffüllen sollte schon geschehen und auf dem Aufgabenblatt steht "sortieren innerhalb der Knoten wird berücksichtigt"
heißt dass wenn ich einen knoten hab der Form

p1 50 p2

und ich will 30 einfügen, dass ich dann innerhalb des Knotens sortieren kann und folgender Knoten entsteht ?

p0 30 p1 50 p2

oder sollte 30 in p1 weiter eingefügt werden

[Le_Coeur]

wenn du meinst knoten auffüllen sollte schon geschehen und auf dem Aufgabenblatt steht "sortieren innerhalb der Knoten wird berücksichtigt"
heißt dass wenn ich einen knoten hab der Form

p1 50 p2

und ich will 30 einfügen, dass ich dann innerhalb des Knotens sortieren kann und folgender Knoten entsteht ?

p0 30 p1 50 p2

oder sollte 30 in p1 weiter eingefügt werden

Vorgestern ein Tutor hat mir gesagt, dass es muss in eine Knote eingefuegt werden (p0 30 p1 50 p2), aber heute hab ich noch im Script gefunden(Seite 156, Beispiel mit 85), dass es soll in p1 weiter eingefuegt werden... Jetzt verstehe ich gar nichts))

[ivoch]

wenn ich einen knoten hab der Form

p1 50 p2

und ich will 30 einfügen, dass ich dann innerhalb des Knotens sortieren kann und folgender Knoten entsteht ?

p0 30 p1 50 p2

Genau.

[eesti]

wenn du meinst knoten auffüllen sollte schon geschehen und auf dem Aufgabenblatt steht "sortieren innerhalb der Knoten wird berücksichtigt"
heißt dass wenn ich einen knoten hab der Form

p1 50 p2

und ich will 30 einfügen, dass ich dann innerhalb des Knotens sortieren kann und folgender Knoten entsteht ?

p0 30 p1 50 p2

oder sollte 30 in p1 weiter eingefügt werden

Vorgestern ein Tutor hat mir gesagt, dass es muss in eine Knote eingefuegt werden (p0 30 p1 50 p2), aber heute hab ich noch im Script gefunden(Seite 156, Beispiel mit 85), dass es soll in p1 weiter eingefuegt werden... Jetzt verstehe ich gar nichts))

kann ich auch 30 in p1 einfügen, denn so ist es im Skript, oder ist das falsch???

Und wie ist es beim Löschen, ist es egal ob ich den nächstkleineren oder den nächstgrößeren verwende, denn dazu gibts irgendwie kein Bsp. ????

[empe]

wenn ich einen knoten hab der Form

p1 50 p2

und ich will 30 einfügen, dass ich dann innerhalb des Knotens sortieren kann und folgender Knoten entsteht ?

p0 30 p1 50 p2

Genau.

Sehe ich auch so. Der hier gegebene Baum ist sozusagen etwas erweitert, verglichen mit dem Standard-m-Wege-Baum im Skript. Dadurch wächst seine Höhe nicht so schnell.
Ich würde also sagen, dass es falsch ist, wenn man es genau wie im Skript macht.

Nachtrag: Ob man den gelöschten Schlüssel durch den nächstkleineren oder nächstgrößeren Schlüssel ersetzt müsste eigentlich egal sein. Im Zweifel kann man ja beide Alternativen zeichnen.

[bruse]

Die Frage kam heute in der Übung auch auf. Wenn man so vorgeht, wie im Skript, entsteht recht schnell ein entarteter Baum, das solltet Ihr vermeiden, d.h. auch in bestehende Knoten einfügen (also 30 nicht in p1 einfügen).

Beim Löschen kann man meines Wissens nach beide Varianten verwenden, wenn sie denn zur Verfügung stehen. Wie immer gilt, dass man in seiner Konvention dann aber auch konsistent sein sollte und nicht mal den linken, mal den rechten nehmen (wenn beide zur Verfügung stehen. Sonst ists ja "eh kloar" ).

[b00m3r]

Macht man dieses einfügen in sortierter Reihenfolge nur in der Wurzel oder macht man das später auch für die unteren Kinder so. Wenn ich das so verfolgen würde, dass man quasi die Knoten immer sortiert einfügt entsteht keine Schwierigkeit beim löschen.
Wohingegen eine Verfolgung des "stumpen" einfügens ohne die Reihenfolge zu beachten zu diesem "kleinsten" Vorgänger oder "größten" Nachfolger des gelöschten Knotens führt.

[quanz]

In dieser Aufgabe wird bei jedem neuen Eintrag der entsprechende Knoten neu sortiert.
Kurz: Jeder Knoten, ob Wurzel, innerer Knoten oder Blatt haben Einträge in sortierter Reihenfolge.

[samy-delux]

Also jetzt nur mal ne ganz kurze Frage (hoffe damit nicht unerlaubt was von der Lösung zu veraten):

Sieht der Baum nach dem Einfügen von 89 & 24 so aus:
###
oder so:
###

Das die Schlüssel in den Knoten sortiert sind ist doch klar oder? Dieser Tip bringt mir irgendwie nichts.
Danke für eine Antwort!

edit: Bitte keine konkreten Hinweise auf die Lösung geben!

[k_b]

@samy_delux: Der Knoten soll nach dem Einfügen von 89 und 24 so aussehen wie deine Version 1. Die Schlüssel sind ja immer sortiert da hast du Recht, aber wenn man es so wie in der 2. Version macht, wie ich es auch zuerst hatte, dann ist die Sortierung ja eher so, dass man die kleineren oder größeren Knoten als die 89 in den Kindern findet und in der ersten Version ist es so, dass die kleineren auch noch im selben Knoten stehen und wenn es größere gäbe die auch (solange bis der Knoten voll ist, dann greift die Knotensplittungsregel aus den Folien)

[k_b]

Sehe ich auch so. Der hier gegebene Baum ist sozusagen etwas erweitert, verglichen mit dem Standard-m-Wege-Baum im Skript. Dadurch wächst seine Höhe nicht so schnell.
Ich würde also sagen, dass es falsch ist, wenn man es genau wie im Skript macht.

Wieso ist der Baum denn anders als der m-Wege Baum im Skript, soll man das an der Aussage erkennen, dass es eine Sortierung inerhalb der Knoten gibt? Das ist doch dann a ber auch wieder Doppeltdeutig und es könnte entweder

###
oder :
###
quote]
gemeint sein, weil beide Wege ergeben eine Sortierung der Knoten?

Gibt es einen Grund, warum es egal ist ob man den größte kleinsten Vorgänger oder den kleinsten größten Nachfolger nach dem Löschen hoch zieht?

Danke schonmal

edit: Bitte keine konkreten Hinweise auf die Lösung geben!

[robert.n]

Also jetzt nur mal ne ganz kurze Frage (hoffe damit nicht unerlaubt was von der Lösung zu veraten):

Sieht der Baum nach dem Einfügen von 89 & 24 so aus:
###
oder so:
###

Das die Schlüssel in den Knoten sortiert sind ist doch klar oder? Dieser Tip bringt mir irgendwie nichts.
Danke für eine Antwort!

Ich habs so wie deine zweite Version. Ich werde aber morgen bevor ich abgebe nochmal nachfragen... das ist mir jetzt zu viel Unsicherheit.

edit: Bitte keine konkreten Hinweise auf die Lösung geben!

[bruse]

Tut Euch den Gefallen und verwendet die erste Version.