Ferienübungsblatt
Moderator: AI 2
- import java.noob
- Windoof-User
- Beiträge: 25
- Registriert: 2. Mär 2014 12:28
Re: Ferienübungsblatt
OK, also muss ich die erst mergen und dann rotieren, weil ich mehr als einen Wert in der Wurzel brauche, ist das jetzt richtig?
Re: Ferienübungsblatt

Bzw. den Wert in der Wurzel benötigst du ja um den Knoten aufzufüllen
- import java.noob
- Windoof-User
- Beiträge: 25
- Registriert: 2. Mär 2014 12:28
Re: Ferienübungsblatt
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
ich hätte jetzt
75 100 200
50/60 90 150 350/400
Re: Ferienübungsblatt
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
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

Re: Ferienübungsblatt
Wie sieht denn dein letzter und vorletzter Schritt aus?import java.noob hat geschrieben:
ich hätte jetzt
75 100 200
50/60 90 150 350/400
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

Re: Ferienübungsblatt
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 !
Vielen Dank im Voraus !
- import java.noob
- Windoof-User
- Beiträge: 25
- Registriert: 2. Mär 2014 12:28
Re: Ferienübungsblatt
Kein Problem, aber gut das wir das geklärt habenSophiaLi1 hat geschrieben: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

Nach Einfügen von 60:SvenF hat geschrieben:
Wie sieht denn dein letzter und vorletzter Schritt aus?
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
Re: Ferienübungsblatt
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....
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....
Re: Ferienübungsblatt
Der Baum hat die Ordnung 2.Stan hat geschrieben:Von welcher Ordnung ist denn der Baum bei der Aufgabe 3?
Re: Ferienübungsblatt
Und jetzt nochmal mit Begründung bitte wovon die Ordnung abhängt und warum dann die Rorate funktion nicht anwendbar sein soll? =)SophiaLi1 hat geschrieben:Der Baum hat die Ordnung 2.Stan hat geschrieben:Von welcher Ordnung ist denn der Baum bei der Aufgabe 3?
Re: Ferienübungsblatt
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.Stan hat geschrieben:Und jetzt nochmal mit Begründung bitte wovon die Ordnung abhängt? =)SophiaLi1 hat geschrieben:Der Baum hat die Ordnung 2.Stan hat geschrieben:Von welcher Ordnung ist denn der Baum bei der Aufgabe 3?
- import java.noob
- Windoof-User
- Beiträge: 25
- Registriert: 2. Mär 2014 12:28
Re: Ferienübungsblatt
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...)
Re: Ferienübungsblatt
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 hat geschrieben: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...)
- import java.noob
- Windoof-User
- Beiträge: 25
- Registriert: 2. Mär 2014 12:28
Re: Ferienübungsblatt
Beim Einfügen ist es aber egal ob ein Knoten nur einen Key hat 

Re: Ferienübungsblatt
Genau (:import java.noob hat geschrieben:Beim Einfügen ist es aber egal ob ein Knoten nur einen Key hat