foo Testat #4

hamiansa
Neuling
Neuling
Beiträge: 7
Registriert: 9. Apr 2014 10:07

foo Testat #4

Beitrag von hamiansa »

Hallo,

wann werden die Musterlösungen für b-tree delete implementiert? Ich habe das letzte foo Testat verhauen und stehe ziemlich unter Druck. Deshalb wäre es echt cool wenn das demnächst mal geschehen würde.
Ich habe auch noch nicht ganz begriffen was es mit der Ordnung und den Mindestanzahl von keys auf sich hat. Ich habe mir das Video angeschaut aber habe es dennoch nicht verstanden.

Ich bin für jeden Hinweis dankbar.

greetz

samir


ps: hat schon jemand eine Lösungsstrategie?

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

Re: foo Testat #4

Beitrag von Prof. Karsten Weihe »

hamiansa hat geschrieben: Ich habe auch noch nicht ganz begriffen was es mit der Ordnung und den Mindestanzahl von keys auf sich hat. Ich habe mir das Video angeschaut aber habe es dennoch nicht verstanden.
Ein Knoten eines B-Baumes hat immer Platz für eine ungerade Anzahl \(N\) von Keys, denn damit klappen Split und Merge. Aus irgendwelchen Gründen hat sich eingebürgert, nicht diese Anzahl \(N\) für die Angabe zu benutzen, wie groß Baumknoten in einem gegebenen B-Baum sind, sondern \(M:=\lceil N/2\rceil\), so dass also umgekehrt \(N=2\cdot M-1\) ist. Die Zahl \(M\) ist die Ordnung des B-Baumes. Solange \(N\) wirklich ungerade ist, stehen \(N\) und \(M\) in einer 1:1-Beziehung, das heißt, es ist egal, ob \(N\) oder \(M\) zur Angabe der Baumknotengröße verwendet wird.

Nun zur Mindestanzahl Keys: Damit die Höhe jedes B-Baumes schön klein bleibt, dürfen Baumknoten nicht beliebig wenige Keys enthalten. Der Erfinder der B-Bäume hat festgestellt, dass alles gut zusammenpasst, wenn jeder Knoten außer der Wurzel mindestens \(M-1=\lfloor N/2\rfloor\) Keys enthält. Wie Sie im Video (hoffentlich) sehen können, passt das haargenau zu Split und Merge.

Klarer geworden?

KW

hamiansa
Neuling
Neuling
Beiträge: 7
Registriert: 9. Apr 2014 10:07

Re: foo Testat #4

Beitrag von hamiansa »

[/quote]
Klarer geworden?

KW[/quote]


Ja, dankeschön. Aber vielleicht könnten Sie mir netterweise die Notation erklären. Ich werde nicht ganz schlau daraus. Ich konnte auch nicht herausfinden wie man die Knoten zählt bzw. wie man auf die ID's kommt. dann bin ich ready für das Testat :D

grüße

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

Re: foo Testat #4

Beitrag von Prof. Karsten Weihe »

hamiansa hat geschrieben:Aber vielleicht könnten Sie mir netterweise die Notation erklären.
Was genau meinen Sie mit "die Notation"?

KW

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

Re: foo Testat #4

Beitrag von Nullmann »

hamiansa hat geschrieben: [...] bzw. wie man auf die ID's kommt.
Die ID's sind weitestgehend zufällig. Zitat aus der Foo-Aufgabenstellung:
Foo hat geschrieben: Die Knoten-ID ist eine frei wählbare Zahl. Ausnahme: die Wurzel hat immer ID = 0.
Das Gute an der Live-Vorschau ist, dass die Knoten grün umrandet werden, wenn man auf das jeweilige Eingabe-Feld klickt. Dadurch kann man relativ leicht (wenn auch immer noch etwas clunky) die ID des jeweiligen Knotens herausfinden.

hamiansa
Neuling
Neuling
Beiträge: 7
Registriert: 9. Apr 2014 10:07

Re: foo Testat #4

Beitrag von hamiansa »

Nullmann hat geschrieben:
hamiansa hat geschrieben: [...] bzw. wie man auf die ID's kommt.
Die ID's sind weitestgehend zufällig. Zitat aus der Foo-Aufgabenstellung:
Foo hat geschrieben: Die Knoten-ID ist eine frei wählbare Zahl. Ausnahme: die Wurzel hat immer ID = 0.
Das Gute an der Live-Vorschau ist, dass die Knoten grün umrandet werden, wenn man auf das jeweilige Eingabe-Feld klickt. Dadurch kann man relativ leicht (wenn auch immer noch etwas clunky) die ID des jeweiligen Knotens herausfinden.

Ich gebe mal die Empfehlung an alle raus die ID's komplett neu zu benennen. Das macht das alles um einiges überschaulicher. Ich persönlich bevorzuge es von rechts nach links die ID's in aufsteigender Zahlenfolge zu benennen. Das macht die Kantenverteilung später auch mega easy.

Benutzeravatar
luedecke
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 124
Registriert: 17. Mär 2015 00:08

Re: foo Testat #4

Beitrag von luedecke »

hamiansa hat geschrieben: Ich gebe mal die Empfehlung an alle raus die ID's komplett neu zu benennen. Das macht das alles um einiges überschaulicher. Ich persönlich bevorzuge es von rechts nach links die ID's in aufsteigender Zahlenfolge zu benennen. Das macht die Kantenverteilung später auch mega easy.
Die Vergabe der ID's hat mit der Visualisierungssoftware der Bäume zu tun -> https://de.wikipedia.org/wiki/Graphviz.

Wir haben an diesem Punkt Fremdsoftware verwendet, da diese Marktführend ist und wir (noch) nicht die Möglichkeit haben, eine äquivalent gute Baumvisualisierung zu realisieren.
Bei Graphen war es wesentlich einfacher umzusetzen...

Nutzt die Zeit und das Highlighting. Wir haben versucht, das bestmögliche rauszuholen :)

h4ktheworld
Windoof-User
Windoof-User
Beiträge: 25
Registriert: 29. Apr 2015 12:34

Re: foo Testat #4

Beitrag von h4ktheworld »

Hat sich geklärt. Die Macher waren einen Schritt voraus :P


Liebe Grüße

Antworten

Zurück zu „Archiv“