B-Tree-insert: Algo korrekt?

KevinK
Erstie
Erstie
Beiträge: 14
Registriert: 20. Apr 2015 12:33

B-Tree-insert: Algo korrekt?

Beitrag von KevinK »

Hallo ich habe folgende Frage bzw Problem.
Und zwar dachte ich (so wird es auch im Video in Wiki erklärt), dass damit der Zeiger p hinab steigen kann der aktuelle Knoten noch nicht voll sein darf. Sprich wenn er voll ist wird er erst geteilt, dass er nicht voll ist, danach kann p erst absteigen.

Im folgenden d3e0cf9fc15b4ebfabd1f62a5b591401
ist Wurzel mit 57/75/86 voll, trotzdem steigt p ab und fügt 57 in das Blatt ein.
Meine Frage ist jetzt ob das doch so gewollt ist dass man einfach in die Wurzel einfügen kann, wenn diese nicht voll ist und dann einfach "rückwärts" splittet oder ein Fehler in foo ist. Es wundert mich nur deshalb so, weil bei delete wird ja auch erst geguckt ob man löschen darf, bevor man hinabsteigt.

Danke schon Mal für eine Antwort und Grüße :)

FloT
Neuling
Neuling
Beiträge: 6
Registriert: 25. Apr 2015 11:21

Re: B-Tree-insert: Algo korrekt?

Beitrag von FloT »

Hallo Zusammen,

Ich habe gerade den Algo das erste mal ausprobiert und die Lösung verstößt direkt gegen mehrere Regeln der Invariante.

Bild
Seed: b2e7f6acab100b9f18eb5b03026592ce

Wenn der Algorithmus schon klausurrelevant ist, dann sollte er doch wenigstens auch für die Klausurvorbereitung funktionieren und bitte nicht erst 1 Woche vorher. :roll:

Grüße

headhumper
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 118
Registriert: 13. Aug 2009 21:25

Re: B-Tree-insert: Algo korrekt?

Beitrag von headhumper »

FloT hat geschrieben:Wenn der Algorithmus schon klausurrelevant ist, dann sollte er doch wenigstens auch für die Klausurvorbereitung funktionieren und bitte nicht erst 1 Woche vorher. :roll:
"Heap: decrease key" ist auch kaputt.
Prof. Karsten Weihe hat geschrieben:Ich möchte generell hinzufügen, dass die Sorgfalt, die Ihnen hier abgefordert wird, nicht höher ist als in vielen Situationen in Ihrem späteren Berufsleben, wo Sie voraussichtlich oft unter deutlich massiverem Druck und deutlich länger als eine halbe Stunde arbeiten werden.
Die Foo-Entwickler machen das hoffentlich nicht "beruflich" :lol:

qo55ciju
Erstie
Erstie
Beiträge: 14
Registriert: 16. Apr 2015 18:21

Re: B-Tree-insert: Algo korrekt?

Beitrag von qo55ciju »

f75e8f16d97b6d38c0866a7d2ad5aa24

die Wurzel hier wird auch nicht gesplittet, obwohl sie voll ist.

robtothein
Mausschubser
Mausschubser
Beiträge: 57
Registriert: 1. Aug 2014 13:33

Re: B-Tree-insert: Algo korrekt?

Beitrag von robtothein »

b54ea265232c71a9adc76b4d503804b6
VG,
robtothein

Jannis
Mausschubser
Mausschubser
Beiträge: 63
Registriert: 15. Apr 2015 17:10

Re: B-Tree-insert: Algo korrekt?

Beitrag von Jannis »

Bei mir hat der Algo zwar bis jetzt korrekt funktioniert, jedoch wertet er das Ergebnis bis jetzt IMMER falsch aus:

Zum Beispiel:

6126087e7af71ca3f36588b21836fd43 - Ergebnisbaum exakt wie in Lösung, allerdings wird sie als falsch gewertet. (Könnte aber auch sein, dass ich mich verschaut habe bei den vielen Werten.. bin aber jetzt öfter durchgegangen und konnte keinen Unterschied feststellen)

b1df38b8629b8ced5db21200b342c451 - Auch hier ist die Lösung scheinbar das Gleiche wie meine Abgabe und dennoch wird sie als nicht korrekt gewertet. Allerdings tritt in der GUI eine seltsame Überkreuzung der Kindknoten im rechten Teilbaum auf.

Hier noch einmal als Bild:
Bild

bekir
Mausschubser
Mausschubser
Beiträge: 61
Registriert: 16. Okt 2014 20:35

Re: B-Tree-insert: Algo korrekt?

Beitrag von bekir »

Jannis hat geschrieben:Bei mir hat der Algo zwar bis jetzt korrekt funktioniert, jedoch wertet er das Ergebnis bis jetzt IMMER falsch aus:

Zum Beispiel:

6126087e7af71ca3f36588b21836fd43 - Ergebnisbaum exakt wie in Lösung, allerdings wird sie als falsch gewertet. (Könnte aber auch sein, dass ich mich verschaut habe bei den vielen Werten.. bin aber jetzt öfter durchgegangen und konnte keinen Unterschied feststellen)

b1df38b8629b8ced5db21200b342c451 - Auch hier ist die Lösung scheinbar das Gleiche wie meine Abgabe und dennoch wird sie als nicht korrekt gewertet. Allerdings tritt in der GUI eine seltsame Überkreuzung der Kindknoten im rechten Teilbaum auf.

Hier noch einmal als Bild:
Bild
Kann sein, dass es an der Wurzel liegt. Die ID der Wurzel muss immer 0 sein, ansonsten ist die Lösung falsch.

Jannis
Mausschubser
Mausschubser
Beiträge: 63
Registriert: 15. Apr 2015 17:10

Re: B-Tree-insert: Algo korrekt?

Beitrag von Jannis »

bekir hat geschrieben: Kann sein, dass es an der Wurzel liegt. Die ID der Wurzel muss immer 0 sein, ansonsten ist die Lösung falsch.
Ahhhh, das habe ich ganz verdrängt. Danke! Klappt jetzt :roll:

james0707007
Neuling
Neuling
Beiträge: 5
Registriert: 12. Jun 2015 20:19

Re: B-Tree-insert: Algo korrekt?

Beitrag von james0707007 »

a277903bead45adeeabab9bf78ce9f23

Hier wird ebenfalls eine volle Wurzel nicht gesplittet. Laut Invariante des Algo-Wikis müsste dies aber eigentlich geschehen ("After i>=0 iterations: 1. Pointer p points to some node of the B-tree on height level i such that n<2M-1 for this node."), da p ja in der 0-ten Iteration auf die Wurzel zeigt...

stanLee
Neuling
Neuling
Beiträge: 5
Registriert: 2. Mai 2015 11:37

Re: B-Tree-insert: Algo korrekt?

Beitrag von stanLee »

auch bei mir klappt insert nicht,

ich bitte die foo-Entwickler darum, die Fehler schnellstmöglich zu beheben

Antworten

Zurück zu „Archiv“