Seite 1 von 1

B-tree insert ist gefixt

Verfasst: 17. Sep 2015 15:59
von Prof. Karsten Weihe
Das Betreff ist die Botschaft.

KW

Re: B-tree insert ist gefixt

Verfasst: 17. Sep 2015 22:11
von Symen
Hallo,

glaub ich habe eine weiter Unstimmigkeit zwischen "B-Tree insert" in foo und wiki gefunden.

Soll in foo ein Wert in den Baum eingefügt werden der auch schon in einem Knoten vorkommt wird in den linken Teilbaum abgestiegen,
dem wiki nach sollte aber in den rechten Teilbaum abgestiegen werden.

Wiki: B-Tree insert:

1. If p.children[0] = void:
...
2. If K < p.keys[1] set k := 0; otherwise, let k ϵ {1,...,p.n} be maxminal such that K >= p.keys[k]
3. If p.children[k].n = 2M-1: call "B-tree: split node into two siplings"
4. If K < p.keys[1] set p := p.children[0]; otherwise, set p := p.children[k] where k ϵ {1,...,p.n} is mayimal such that K >= p.keys[k]

Konkreter Fall in foo:
https://foo.algo.informatik.tu-darmstad ... 4699c1af0d

Re: B-tree insert ist gefixt

Verfasst: 18. Sep 2015 09:25
von Nullmann
KW hatte bisher in anderen Threads (die ich nicht mehr heraussuche) zwei Statements abgeliefert:

1) Es werden 1:1 Foo Aufgaben dran kommen

2) Es wird keine Unstimmigkeiten in der Klausur geben (Dies war als Antwort auf die Frage, ob bei Prim egal ist, welche Kante man zuerst nimmt, wenn es zwei gleich schwere gibt)

Zu 1) würde ich dann auch mal schätzen, dass die Lösungen der ML von Foo stammen werden.
2) ist wie bei dir der gleiche Fall: Der generelle Algorithmus lässt an dieser Stelle dem Programmierer eine Freiheit, die natürlich in einer konkreten Implementierung irgendwie gesetzt werden muss.

Aus diesen zwei Punkten heraus würde ich schätzen, dass es in der Klausur "Tie Breaker" geben wird, in denen nochmal explizit drauf eingegangen wird, was wann zu tun ist, wenn es der allgemeine Algorithmus nich genau vorgibt.
Jedoch ist es wohl anzuraten, sich die Foo-Variante anzueignen, um so die Klausuraufgabe schneller lösen zu könnnen, weil die Tie Breaker im Zweifelsfall denen der Foo-Implementierung entsprechen.

Mfg,
Nullmann

Re: B-tree insert ist gefixt

Verfasst: 18. Sep 2015 17:23
von mProg
Ich habe auch das Problem Symen geschrieben hat, gehabt und es ist zweideutig. Es sind nur noch einige Tagen bis zur Klausur übrig und Foo ist ein wichtiger Bestandteil zur Vorbereitung für die Klausur. Jedoch weiß man nicht, ob man sich bei diese Widersprüche an Foo oder Wiki halten soll?

Re: B-tree insert ist gefixt

Verfasst: 18. Sep 2015 17:41
von felicis
ich glaube man kann diese Unstimmigkeit lösen, indem man die Beschreibung im Wiki folgendermaßen anpasst:

...
2. If K <= p.keys[1] set k := 0; otherwise, let k ϵ {1,...,p.n} be maxminal such that K > p.keys[k]
...
4. If K <= p.keys[1] set p := p.children[0]; otherwise, set p := p.children[k] where k ϵ {1,...,p.n} is mayimal such that K > p.keys[k]

Durch das "<=" zu Beginn wird auch bei gleichem Wert nach links runter gegangen; bei echt größerem wird dann nach rechts gegangen. Das ist für beide Zeilen notwendig, da ja das Ziel-Child zuerst auf genug Platz gecheckt wird!

Gruß
felicis

Re: B-tree insert ist gefixt

Verfasst: 18. Sep 2015 18:28
von felicis
Mir fällt gerade auf, dass dann ebenso der Pseudocode "B-TREE-INSERT-NONFULL(x,k)" angepasst werden müsste (in Zeile 9):
"9 else while i >= 1 and k <= x.key_(i)"
anstatt
"9 else while i >= 1 and k < x.key_(i)"

PS: Falls dieser Fehler auch bei einem leaf auftritt (nicht nur bei Knoten), muss wieder die Implementation (Induction Step: 3. Zeile) und der dazugehörige Pseudocode angepasst werden:
"1. Let k \(\in\) {1,...,p.n} be the minimal position such that K <= p.keys[j]."
anstatt von
"1. Let k \(\in\) {1,...,p.n} be the minimal position such that K < p.keys[j]."
Für den Pseudocode gilt dann auch (in "B-TREE-INSERT-NONFULL(x,k)"):
"3 while i >= 1 and k <= x.key_i"
anstatt
"3 while i >= 1 and k < x.key_i"

PS2: Ist in der vierten Zeile von Implementation/Induction Step nicht auch ein Fehler??
"2. For j = p.n, ... ,k (in that order), set p.keys[j+1] := p.keys[j]."
anstatt von
"2. For j = p.n, ... ,k (in that order), set p.keys[j+1] := p.keys[k]."

PS3: Und sollte im Pseudocode von "B-TREE-INSERT-NONFULL(x,k)" in Zeile sechs nicht das stehen:
"6 x.key_(i+1) = k"
anstatt von
"6 x.key_(i)+111 = k"???

Re: B-tree insert ist gefixt

Verfasst: 19. Sep 2015 13:18
von headhumper
Wurde die Aufgabe auf die Art und Weise repariert, dass der Fall des Splittens einfach nicht mehr Auftritt :?:
Habe die Aufgabe gerade 10x hintereinander gemacht und musste 10x einfach nur den Wert ins richtige Blatt schreiben.

Re: B-tree insert ist gefixt

Verfasst: 19. Sep 2015 15:03
von CryNickSystems
Bei mir trat gestern noch ein Split auf, also alles gut :D

Re: B-tree insert ist gefixt

Verfasst: 23. Sep 2015 10:44
von SenZe
Bei meinen 20 Versuchen gerade eben musste ich nicht einmal einen split auf der Wurzel machen, nur einmal in einem Blatt...