H 8.4

linn
Mausschubser
Mausschubser
Beiträge: 77
Registriert: 15. Okt 2008 21:16

H 8.4

Beitrag von 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
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 199
Registriert: 3. Mär 2004 10:51

Re: H 8.4

Beitrag von 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
Mausschubser
Mausschubser
Beiträge: 82
Registriert: 15. Apr 2009 15:16
Kontaktdaten:

Re: H 8.4

Beitrag von 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

Benutzeravatar
Le_Coeur
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 135
Registriert: 18. Apr 2009 12:39
Kontaktdaten:

Re: H 8.4

Beitrag von Le_Coeur »

Niggi hat geschrieben: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
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 199
Registriert: 3. Mär 2004 10:51

Re: H 8.4

Beitrag von ivoch »

Niggi hat geschrieben: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
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 116
Registriert: 6. Okt 2008 20:59
Wohnort: Darmstadt

Re: H 8.4

Beitrag von eesti »

Le_Coeur hat geschrieben:
Niggi hat geschrieben: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. ????

:roll:

empe
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 118
Registriert: 14. Jan 2008 14:24

Re: H 8.4

Beitrag von empe »

ivoch hat geschrieben:
Niggi hat geschrieben: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.

Benutzeravatar
bruse
Kernelcompilierer
Kernelcompilierer
Beiträge: 412
Registriert: 2. Aug 2006 22:42

Re: H 8.4

Beitrag von 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" :-)).
Un hombre de frente a una ventana
Súper lúcida la mirada
Recorre el paisaje y no,
no es su interior, es luna.

b00m3r
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 182
Registriert: 10. Okt 2005 11:02

Re: H 8.4

Beitrag von 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
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 103
Registriert: 1. Okt 2007 19:32

Re: H 8.4

Beitrag von 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
Mausschubser
Mausschubser
Beiträge: 64
Registriert: 21. Okt 2008 18:59

Re: H 8.4

Beitrag von 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
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 213
Registriert: 15. Mär 2009 12:06

Re: H 8.4

Beitrag von 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
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 213
Registriert: 15. Mär 2009 12:06

Re: H 8.4

Beitrag von k_b »

empe hat geschrieben: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
samy-delux hat geschrieben: ###
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
Nerd
Nerd
Beiträge: 673
Registriert: 29. Sep 2008 19:17

Re: H 8.4

Beitrag von robert.n »

samy-delux hat geschrieben: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!

Benutzeravatar
bruse
Kernelcompilierer
Kernelcompilierer
Beiträge: 412
Registriert: 2. Aug 2006 22:42

Re: H 8.4

Beitrag von bruse »

Tut Euch den Gefallen und verwendet die erste Version.
Un hombre de frente a una ventana
Súper lúcida la mirada
Recorre el paisaje y no,
no es su interior, es luna.

Antworten

Zurück zu „Archiv“