Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
11.6 B-Tree
Kann es zufaellig sein, dass es einen Fehler im EST gibt? Die frisch von der AuD-Homepage heruntergeladenen Dateien kompilieren nicht einmal. Vielleicht gibts OverflowNode nicht?
Da ich keinen 2. Thread oeffnen moechte: Wenn ich’s richtig verstanden habe, sollen bei der 11.5 auch Baeume als Heap erkannt werden, wenn sie die Linksvollstaendigkeit nicht erfuellen, aber das andere Kriterium, oder?
11.1
was für bäume sind den gemeint in der aufgabe 11.1 a)? oder binär? sollen die balanciert sein oder nicht? ist auch einfach ein entarteter Baum möglich? ^^ oh man…oder mindestens ein verzweigung? oder darf man hier machen was man will und alles ist richtig?
P.S.: falls jemand noch nen nettes Tool sucht. “yEd” scheint ganz angenehm zu sein um Bäume zu malen oder auch andere Diagramme…
Nein, davon würde ich nicht ausgehen. Lies dir nochmal Folie 12-8 durch.
das habe ich schon auch schon im Vorfeld, aber meine frage bleibt ja bestehen. Wenn entartete Bäume erlaubt sind dann wär die maximale höhe n - 1. Ja schon klar das ein Knoten entweder 0 oder mehrere Nachfolger hat, aber dann müsst man ja eine Binärbaum hernehmen… aber da bleibt ja die Frage muss jedes Blatt einen reelen inhalt haben. wäre also wieder die frage ob ein entarteter Baum auch zählt.
Ein Baum ist eine Struktur aus Knoten und Kanten. Jeder Knoten (außer der Wurzel) hat genau einen Vorgänger. Jeder Knoten hat beliebig viele Nachfolger. Es gibt keine Zyklen.
also ist schon klar was die defintion ist, bitte mal meine Frage lesen… wäre auch ein entarteter Baum ein Baum im Sinne der Aufgabenstellung, das ist doch die Frage, den in diesem Fall wäre die maximale höhe n-1. Auch ist ja die Frage ob jeder knoten auf jeder höhe voll belegt sein muss… je nachdem welche Anforderungen hier gestellt sind unterscheidet sich die Antwort.
Whitespace: auch stimmt deine Antwort laut Folien nicht, den ein Baum hat entweder 0 oder mehrere Nachfolger, hat nämlich jeder knoten nur einen Nachfolger ist es eine liste. zumindest laut Definition der Folie. Ausnahme sind halt entartete Bäume, diese haben zwar mindestens zwei Verzweigungen, aber es ist halt nur einer belegt. das ist ja die ganze Zeit meine Frage. Hat vielleicht mal noch jemand nen Hinweis, außer lies die Folie? 
Hier sind die Folien leider etwas ungenau/falsch.
Eine einfach-verkettete Liste ist eine spezielle Art von Baum.
Mehr als die Definition von vorhin kann ich dir nicht sagen, ohne die Lösung bekannt zu geben.
Überprüfe einfach, ob deine Struktur die Definition des Begriffs aus der Aufgabenstellung erfüllt.
Damit sind alle deine Fragen erschöpfend beantwortet.
Problem gelöst, die frage kam in der mini klausur und ich habs so geschrieben wie ich mir gedacht hab und es war richtig. 
Ausgabe 11.6
Hallo allerseits,
leider erhalten ich bei der Aufgabe 11.6 ein !, obwohl die Ausgabe/testcases meiner Meinung nach korrekt ist.
Meine Ausgabe ist:
Tree:
→ 17 21 23
Tree:
→ 21
→ 2 8 9 17
→ 22 23
Tree:
→ 9 21
→ 2 8
→ 13 17 18 19
→ 22 23
Tree as JSON String:
{
node: [9, 21],
children: [{
node: [2, 8]
}, {
node: [13, 17, 18, 19]
}, {
node: [22, 23]
}]
}
18 in tree? true
2 in tree? true
116 in tree? false
-1 in tree? false
Die fehlenden Einrückungen bei der d) sollten ja keinen Fehler erzeugen.
Hat jemand vielleicht eine Idee, warum ich ein ! habe?
Danke.
Sind sonst alle B-Baum-Eigenschaften korrekt implementiert?
Soweit ich es sehe ja.
Es könnte noch eine Sachen sein. Ich habe die rekursive Arbeit im BTreeNode jeweils in eine eigene (private) Methode ausgelagert. dh. zb. hasKey(Integer key) ruft eine eigene Methode auf, die die rekursion durchführt. Aber dadurch wird ja immer noch ein das Problem rekursiv gelöst. Sollte also kein Problem sein?
Ich hätte auch eine Frage zum B-Tree. Wie kann ich denn von einer Node auf den Elternknoten zugreifen? Schließlich muss beim splitten der mittlere key ja in den Elternknoten, aber ich komme einfach nicht darauf, wie ich dann darauf zugreifen kann :-/
Auf den Elternknoten zugreifen kannst du tatsächlich nicht. Du solltest dir für split also ein anderes Vorgehen überlegen.
Und wie kann man dann bei der Split-Methode vorgehen?
Ich komm da irgendwie überhaupt nicht weiter
Das Zauberwort steht auf dem Aufgabenblatt: Rekursion
Wenn du mit Hilfe von Rekursion von der Wurzel bis zu den Blättern hinabsteigst, musst du zwangsläufig am Ende wieder eine Ebene nach oben steigen. Diese Tatsache und der Rückgabewert der rekursiven Funktion könnten dir von Nutzen sein.
Warum muss insert von BTreeNode einen OverFlowNode zurückgeben? Es gibt ja schließlich auch den Fall, dass es gar nicht erst zu einem Überlauf kommt.
Es steht ja nirgendwo, dass du immer einen OverflowNode zurueckgeben musst ;). Das ist nur noetig wenns auch wirklich zum Ueberlauf kommt.
Darf ein Key öfters eingetragen werden? Hab ich was überlesen?
Okay, das klärt schon mal Einiges. Danke für die Antwort 
Falls es nun aber mehrmals zum Überlauf kommt, verändert sich der von split zurückgegebene Überlaufknoten ja. Welcher soll dann von insert zurückgegeben werden? Wenn ich stur nach jedem Überlauf den dementsprechenden Knoten zurückgeben würde, würde ich ja die Korrektur der höheren Ebenen unterbrechen, oder liegt da bei mir irgendwo ein Verständnisfehler vor?