B-tree insert ist gefixt

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

B-tree insert ist gefixt

Beitrag von Prof. Karsten Weihe »

Das Betreff ist die Botschaft.

KW

Symen
Erstie
Erstie
Beiträge: 19
Registriert: 5. Mai 2013 12:25

Re: B-tree insert ist gefixt

Beitrag 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

Nullmann
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 139
Registriert: 21. Apr 2015 20:59

Re: B-tree insert ist gefixt

Beitrag 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

mProg
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 147
Registriert: 25. Apr 2015 00:10

Re: B-tree insert ist gefixt

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

Benutzeravatar
felicis
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 114
Registriert: 14. Apr 2015 20:25

Re: B-tree insert ist gefixt

Beitrag 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

Benutzeravatar
felicis
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 114
Registriert: 14. Apr 2015 20:25

Re: B-tree insert ist gefixt

Beitrag 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"???

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

Re: B-tree insert ist gefixt

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

CryNickSystems
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 119
Registriert: 30. Apr 2015 18:27

Re: B-tree insert ist gefixt

Beitrag von CryNickSystems »

Bei mir trat gestern noch ein Split auf, also alles gut :D

SenZe
Erstie
Erstie
Beiträge: 20
Registriert: 13. Dez 2011 21:03

Re: B-tree insert ist gefixt

Beitrag von SenZe »

Bei meinen 20 Versuchen gerade eben musste ich nicht einmal einen split auf der Wurzel machen, nur einmal in einem Blatt...

Antworten

Zurück zu „Archiv“