Ferienübungsblatt

[import java.noob]

OK, also muss ich die erst mergen und dann rotieren, weil ich mehr als einen Wert in der Wurzel brauche, ist das jetzt richtig?

[SvenF]

Jap meines Wissens und der Erklärung von den Videos nach JA.

Bzw. den Wert in der Wurzel benötigst du ja um den Knoten aufzufüllen

[import java.noob]

Vielen Dank für die Geduld, was hast du denn als Endergebnis raus?

ich hätte jetzt
75 100 200
50/60 90 150 350/400

[SophiaLi1]

Hey,
Ich muss mich korrigieren: F_1 und F_2 sind doch zum Einsetzen in F_i gedacht, hab gerade nochmal nachgefragt. Die letzte Aufgabe ist falsch und wenn es klappt, wird noch eine korrigierte Aufgabenstellung hochgeladen. Bei der B-Baum Aufgabe ist alles, was ich gesagt habe richtig.
Sorry

[SvenF]

ich hätte jetzt
75 100 200
50/60 90 150 350/400

Wie sieht denn dein letzter und vorletzter Schritt aus?

Ich setzte mal beim Einfügen der 60 ein, dazu musste ich den linkesten Knoten Spliten
Wurzel war dann 200, darunter links 75/100 und rechts die 350
Blätter waren dann 50/60 90 150/180 300 400
Darauf hin folgt löschen 180, das geht einfach da kein Knoten minimal ist.

Zum Löschen der 300 muss wieder ziemlich gemergt werden nach meiner Ansicht.
Erst das gesplittete Ding, da es durch entfernen der 180 minimal wurde, Mergen. ich bekomme dann

200
75 350
50/60 90/100/150 300 400
Dann Merge ich die Wurzel, zu
75/200/350
50/60 90/100/150 300 400

und nun müsste ich rotieren um die 300 löschen zu können, da kein Merge geht und der knoten minimal ist.
Die 200 habe ich rotiert, und der unmittelbare Vorgänger muss ja den Platz einnehmen. das wäre die 150. ich komme somit auf

75/150/350
50/60 90/100 200 400,

kann aber sein dass ich iwo was übersehen habe, war etwas spät gestern als ich die Aufgabe gemacht hatte.

Ich versuche später nochmal meinen Weg zu kontrollieren und ggf. zu korrigieren, wenn ich was falsch gemacht habe bin zZ. an einem anderen Thema am lernen

[wac]

Hallo, kann mir jemand erklären , was mit dem Rekursionsschritt (14,2,3,0,1) in der Aufgabe 1.2 gemeint ist !! Sollen wir eigentlich das ganze Verfahren zeichnen ?
Vielen Dank im Voraus !

[import java.noob]

Hey,
Ich muss mich korrigieren: F_1 und F_2 sind doch zum Einsetzen in F_i gedacht, hab gerade nochmal nachgefragt. Die letzte Aufgabe ist falsch und wenn es klappt, wird noch eine korrigierte Aufgabenstellung hochgeladen. Bei der B-Baum Aufgabe ist alles, was ich gesagt habe richtig.
Sorry

Kein Problem, aber gut das wir das geklärt haben

Wie sieht denn dein letzter und vorletzter Schritt aus?

Nach Einfügen von 60:

200
75/100 350
50/60 90 150/180 300 400

Wenn man dann die 180 löschen will braucht man in der Wurzel ja mehr als einen Wert, deswegen habe ich eine Rotation durchgeführt und die 300, 350 und 400 gemergt

100
75 200
50/60 90 150/180 300/350/400

Dann habe ich wieder die oberen drei gemergt, daraus folgt dann

75/100/200
50/60 90 150/180 300/350/400

Und aus diesem Baum kann man die 180 und 300 ganz leicht löschen

[Stan]

Von welcher Ordnung ist denn der Baum bei der Aufgabe 3?

Wenn ich es richtig verstanden habe, dann ist den BBaum der Ordnung 3, weshalb jeder Knoten mindestens m-1 Keys haben muss also in diesem Fall 2 Keys.

Ein Abstieg auf einen Knoten beim Löschen ist nur dann möglich, wenn sie m-1 Keys beinhalten. Also in diesem Fall 2 Keys. Ich bin mitlerweile der Meinung, dass der Baum der Ordnung 2 ist, aber warum?(wegen 2m-1= max 3 keys?) Hängt es denn nicht von der Tiefe des Baumes ab? Bzw. wie genau ist die Ordnung definiert?

Wenn wir von Ordnung 2 ausgehen, dann kann man nur hinabsteigen, wenn Auf den Knoten m-1 Werte sich befinden, was in diesem Fall bei der 400 der Fall wäre, man könnte also Runter.Eine Rotate funktion darf man anweden,wenn der eine Knoten n>m-1 keys enthält und der andere m-1. Was in diesem Fall zutrifft. Es wurde von vorgängern allerdings behauptet, dass man Merge auf die Wurzel anwenden muss, da ein Abstieg nicht erlaubt ist... das würde dann stimmen, denn es müssten mindestens zwei Werte auf dem Knoten sein, was nicht zutrifft. Dann wäre allerdings der gegebene Baum kein BBaum, weil Definitionsbedingungen verletzt sind.

Also eigentlich hängt es bei mir derzeit an der Ordnung des Baumes....

[SophiaLi1]

Von welcher Ordnung ist denn der Baum bei der Aufgabe 3?

Der Baum hat die Ordnung 2.

[Stan]

Von welcher Ordnung ist denn der Baum bei der Aufgabe 3?

Der Baum hat die Ordnung 2.

Und jetzt nochmal mit Begründung bitte wovon die Ordnung abhängt und warum dann die Rorate funktion nicht anwendbar sein soll? =)

[SophiaLi1]

Von welcher Ordnung ist denn der Baum bei der Aufgabe 3?

Der Baum hat die Ordnung 2.

Und jetzt nochmal mit Begründung bitte wovon die Ordnung abhängt? =)

Davon, wie viele maximale Nachfolger es gibt, das sind nämlich 2M, in der Aufgabe gibt es maximal 4 Nachfolger, also hat der Baum die Ordnung M=2.

[import java.noob]

Das mit der Ordnung sieht man dass jeder Knoten maximal 3 key haben darf und dass man rotate nicht anwenden darf liegt daran dass wenn man zu einem Knoten absteigt, der Knoten mehr als die minimale Anzahl keys haben muss (Wenn ich das richtig verstanden habe...)

[Stan]

Das mit der Ordnung sieht man dass jeder Knoten maximal 3 key haben darf und dass man rotate nicht anwenden darf liegt daran dass wenn man zu einem Knoten absteigt, der Knoten mehr als die minimale Anzahl keys haben muss (Wenn ich das richtig verstanden habe...)

Ich glaube habs jetzt, zu dem schluss bin ich auch gekommen, es heißt nicht mindestens m-1 werte sondern mehr als m-1 werte! xD diese Feinheiten...^^

[import java.noob]

Beim Einfügen ist es aber egal ob ein Knoten nur einen Key hat

[SophiaLi1]

Beim Einfügen ist es aber egal ob ein Knoten nur einen Key hat

Genau (: