H9.5 d) ii)

VMann
Mausschubser
Mausschubser
Beiträge: 57
Registriert: 16. Apr 2009 11:51

H9.5 d) ii)

Beitrag von VMann »

Für das Einfügen im B+ Baum steht in den Folien:
- Innere Knoten genau wie beim B-Baum
- Blattknoten nach gleichem Prinzip, muss garantieren, dass größter Schlüssel
aus dem neuen Knoten als Wegweiser in den Elternknoten kopiert wird
Ist es erlaubt, stattdessen den kleinsten Schlüssel aus dem neuen Knoten als Wegweiser zu nutzen? Das würde für mich mehr Sinn ergeben, da ich in der Aufgabe immer größere Schlüssel anbaue. Mit dem größten Schlüssel käme ich ja zu einer minimalen Besetzung.
Computer tun nicht das, was du von ihnen willst, sie tun das, was du ihnen sagst.

Benutzeravatar
klubbhead
Neuling
Neuling
Beiträge: 10
Registriert: 20. Apr 2009 17:17

Re: H9.5 d) ii)

Beitrag von klubbhead »

VMann hat geschrieben:Ist es erlaubt, stattdessen den kleinsten Schlüssel aus dem neuen Knoten als Wegweiser zu nutzen?
Es ist nicht nur erlaubt, sondern erfordert: die Aufgabestellung laut "Hinweis: wenn ein Split in den Blättern auftritt, kopieren Sie den kleinsten Schlüssel aus dem neuen Knoten als Wegweiser in den Elternknoten."

tobiasp
Mausschubser
Mausschubser
Beiträge: 70
Registriert: 5. Okt 2008 23:08

Re: H9.5 d) ii)

Beitrag von tobiasp »

wie sollen denn die Schlüssel bei einem Split aufgeteilt werden? Im Härderskript gibts da leider keine eindeutige Aussage dazu :( Einmal steht da, dass man die vorhandenen Schlüssel halbe-halbe aufteilt und den neuen einsortiert, aber dann ist da noch das Beispiel, wo die 45 eingefügt wird...

Also angenommen man hat den Knoten (1|2) und will 3 einfügen: Soll dann (1|2) <-> (3| ) oder (1| ) <-> (2|3) entstehen? Indexknoten oben drüber interessieren mal nicht :)

grüße,
Tobi

Christian M.
Mausschubser
Mausschubser
Beiträge: 62
Registriert: 14. Okt 2008 17:16

Re: H9.5 d) ii)

Beitrag von Christian M. »

Ich würde sagen (1|2) <-> (3| ).

Bekommt denn jemand bei ii) einen anderen B+-Baum als zuvor raus?! Ich weiß nicht ob ich das bulk-loading falsch verstehe, aber dort nehme ich die vorsortierten Daten und lade immer einen (oder hier zwei) Werte auf einmal rein, und eventuell muss ich splitten. Das ergibt allerdings den gleichen Baum wie bei ii), wo ich dann eben die Werte nur einzeln und aus einem B-Baum kriege, aber solange ich bei beiden immer die kleinsten Werte bekomme ergibt das doch keinen Unterschied, woher ich sie bekomme? Und genau nach Unterschieden wird bei iii) gefragt ...

jaenschi
Windoof-User
Windoof-User
Beiträge: 25
Registriert: 15. Jan 2009 21:45

Re: H9.5 d) ii)

Beitrag von jaenschi »

Ich würde sagen (1| ) <-> (2|3).

Dann kommt da auch was anderes raus als beim bulk-loading. Ansonsten würde das ja echt keinen Sinn machen.

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

Re: H9.5 d) ii)

Beitrag von bruse »

Die Musterlösung verwendet (1,2) <> (3,leer). Das ist auch mit Härder kompatibel: Der überschüssige Knoten (wegen ungerader Knotenzahl) kommt nach links.

Zum Problem der Unterschiede: Es gibt zwei Möglichkeiten: Ihr habt euch unterwegs vertan, oder es gibt keine. Ich würde sorgfältig überprüfen, ob ich alles richtig gemacht habe, und davon ausgehend dann mein Ergebnis beschreiben, vielleicht mit Begründung.
Un hombre de frente a una ventana
Súper lúcida la mirada
Recorre el paisaje y no,
no es su interior, es luna.

h4ck4
Mausschubser
Mausschubser
Beiträge: 91
Registriert: 18. Mai 2009 20:50
Kontaktdaten:

Re: H9.5 d) ii)

Beitrag von h4ck4 »

Ok! Wenn die Musterlösung das so sagt! :D
Dann kommen bei mir aber keine Unterscheide zwischen bulk loading Baum und dem Baum aus ii) raus?! :roll:
Naja, werd ich wohl akzeptieren müssen....
Die andere Variante (1,_) (2,3), wie ich es erst gemacht habe, läuft auf einen anderen Baum raus, wo die Blätter minimal besetzt sind...da würde es schon unterschiede geben ;-P
Zuletzt geändert von h4ck4 am 19. Jun 2009 13:15, insgesamt 1-mal geändert.

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

Re: H9.5 d) ii)

Beitrag von bruse »

Ich habe diese Frage schon beantwortet. Noch expliziter werde ich es nicht machen, sonst könnte ich ja gleich die Lösung hier reinstellen. Ein bisschen Eigenleistung sollte ja schon dabei sein :-)
Un hombre de frente a una ventana
Súper lúcida la mirada
Recorre el paisaje y no,
no es su interior, es luna.

h4ck4
Mausschubser
Mausschubser
Beiträge: 91
Registriert: 18. Mai 2009 20:50
Kontaktdaten:

Re: H9.5 d) ii)

Beitrag von h4ck4 »

Ok Danke! : :)

sina
Windoof-User
Windoof-User
Beiträge: 35
Registriert: 27. Mai 2009 13:58

Re: H9.5 d) ii)

Beitrag von sina »

ich habe mir zwar bereits die Beiträge zu dieser Teilaufgaben durchgelesen, aber ich bin mir trotzdem nicht wirklich sicher ob ich es ganz richtig verstanden habe, daher wollte ich fragen, ob zumindest der anfang dieses BAumes so geht:

wenn ich die ersten 3 Telefonnummern (1, 2,3)in B+_baum einfüge erhalte ich dann:

2
/ \
1 2 <-> 3

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

Re: H9.5 d) ii)

Beitrag von linn »

seh ich das richtig, das wir einmal im B-Baum alle knoten löschen sollen (und das dann immer zeichnen) und dazu noch in nen frischen B+-baum die knoten einfügen sollen (und da auch alle schritte zeichnen)?

Sprich in Hausübung 9 sollen wir insgesamt 4*(rotationen+splitten+konkatenationen) Graphen zeichnen!?

sina
Windoof-User
Windoof-User
Beiträge: 35
Registriert: 27. Mai 2009 13:58

Re: H9.5 d) ii)

Beitrag von sina »

ja anscheinend,,, aber wie machen ich genau den b+-baum mich verwirrt der hinweis,im skript ist es doch genau anders rum,oder verstehe ich das falsch?

Benutzeravatar
Blub
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 244
Registriert: 24. Dez 2007 14:06

Re: H9.5 d) ii)

Beitrag von Blub »

linn hat geschrieben:seh ich das richtig, das wir einmal im B-Baum alle knoten löschen sollen (und das dann immer zeichnen) und dazu noch in nen frischen B+-baum die knoten einfügen sollen (und da auch alle schritte zeichnen)?

Sprich in Hausübung 9 sollen wir insgesamt 4*(rotationen+splitten+konkatenationen) Graphen zeichnen!?
so habe ich es auch verstanden, ja.


@ Sina
Bei mir sieht das so aus:

Code: Alles auswählen

       3
      /   \
    /       \
1 2 <-> 3
//edit. Hm das sollte eigentlich anders aussehen ^^ aber egal :p ich denke man weiss was gemeint ist.

Zum Thema Hinweis. Ich mag die Hinweise die da ständig geben werden generell nicht. Und Hinweis ist bei mir keine Aufforderung. Also überlese ich den Hinweis und mache es so wie es in den Folien steht.
Tutor GDI II SS12
Tutor Trusted Systems WS11/12, Tutor GDI II SS11
Tutor Trusted Systems WS10/11, GDI I WS10/11
Tutor GDI II SS10, Tutor Trusted Systems WS09/10

sina
Windoof-User
Windoof-User
Beiträge: 35
Registriert: 27. Mai 2009 13:58

Re: H9.5 d) ii)

Beitrag von sina »

hm...wenn du das so weiter machst kommt bei dir dann der bulk-loading baum aus b raus???denn das würde ja sinn amchen,dass baum aus b) rauskommt

Benutzeravatar
Blub
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 244
Registriert: 24. Dez 2007 14:06

Re: H9.5 d) ii)

Beitrag von Blub »

sina hat geschrieben:hm...wenn du das so weiter machst kommt bei dir dann der bulk-loading baum aus b raus???denn das würde ja sinn amchen,dass baum aus b) rauskommt
genau das ist meine Intention dabei. Ein naiver Ansatz für um eine sequentielle liste in einen B+-Baum zu übertragen ist ja, einfach nur die sortierte Liste in einen leeren B+-Baum der reihe nach zu adden. Es macht also sinn das der selbe Baum rauskommt.
Ich sehe auch nicht sonderlich viel sinn darin den kleinsten wert des Knotens zu nehmen und in den Elternknoten zu packen. Würde man dies machen, würden ofc bei der iii ein anderer baum rauskommen, da bulk loading in den folien anders beschrieben ist. Aber es ist halt auch nicht sinnvoll ständig zwischen den Methoden zu wechseln, also einmal wird der Wert wenn Elternknotenwert == einzufügender Wert links eingeordnet und einmal rechts. Beim Bulk Loading wird der wert dann rechts eingeordnet, und so mache ich es bei der d. ii auch. So kommt bei mir der selbe Baum wie beim Bulk loading raus. Bei dir auch?
Tutor GDI II SS12
Tutor Trusted Systems WS11/12, Tutor GDI II SS11
Tutor Trusted Systems WS10/11, GDI I WS10/11
Tutor GDI II SS10, Tutor Trusted Systems WS09/10

Antworten

Zurück zu „Archiv“