Seite 1 von 1

B-Tree-insert: Algo korrekt?

Verfasst: 3. Sep 2015 14:50
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 :)

Re: B-Tree-insert: Algo korrekt?

Verfasst: 8. Sep 2015 22:42
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

Re: B-Tree-insert: Algo korrekt?

Verfasst: 8. Sep 2015 23:15
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:

Re: B-Tree-insert: Algo korrekt?

Verfasst: 8. Sep 2015 23:33
von qo55ciju
f75e8f16d97b6d38c0866a7d2ad5aa24

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

Re: B-Tree-insert: Algo korrekt?

Verfasst: 9. Sep 2015 15:21
von robtothein
b54ea265232c71a9adc76b4d503804b6

Re: B-Tree-insert: Algo korrekt?

Verfasst: 10. Sep 2015 10:41
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

Re: B-Tree-insert: Algo korrekt?

Verfasst: 10. Sep 2015 13:17
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.

Re: B-Tree-insert: Algo korrekt?

Verfasst: 10. Sep 2015 17:03
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:

Re: B-Tree-insert: Algo korrekt?

Verfasst: 14. Sep 2015 20:54
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...

Re: B-Tree-insert: Algo korrekt?

Verfasst: 14. Sep 2015 20:57
von stanLee
auch bei mir klappt insert nicht,

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