import java.noob hat geschrieben:
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
Ferienübungsblatt
Moderator: AI 2
- import java.noob
- Windoof-User
- Beiträge: 25
- Registriert: 2. Mär 2014 12:28
Re: Ferienübungsblatt
@Sophia: Kannst du mir vllt. sagen ob diese Vorgehensweise korrekt ist?
Re: Ferienübungsblatt
Bis dahin ist es richtig. Wenn du nun die 180 löschen willst, löschst du sie einfach aus dem Blatt ohne eine zusätzliche Option.import java.noob hat geschrieben:
Nach Einfügen von 60:
200
75/100 350
50/60 90 150/180 300 400
Nachtrag: 50/60 90 150/180 sind Nachfolger von 75/100
- import java.noob
- Windoof-User
- Beiträge: 25
- Registriert: 2. Mär 2014 12:28
Re: Ferienübungsblatt
kommt dann aber aufs gleiche hinaus nur dass ich die 180 früher weglassen kann, oder?
Re: Ferienübungsblatt
Was meinst du damit?
Re: Ferienübungsblatt
Ich glaube er will auf
"Beim Löschen gilt die Invariante, dass der Laufpointer p nur auf Knoten zeigt, die mehr als minimale Anzahl Keys haben, also mehr als ein Key bei der Wurzel beziehungsweise mehr als M-‐1 Keys bei jedem anderen Knoten."
dann könnte man doch die 180 nicht einfach löschen?
"Beim Löschen gilt die Invariante, dass der Laufpointer p nur auf Knoten zeigt, die mehr als minimale Anzahl Keys haben, also mehr als ein Key bei der Wurzel beziehungsweise mehr als M-‐1 Keys bei jedem anderen Knoten."
dann könnte man doch die 180 nicht einfach löschen?
Re: Ferienübungsblatt
Achso, das meint er. Okay, da die Wurzel eine Ausnahmebehandlung darstellt und nur in dem Fall "Die Wurzel selbst hat nur einen Key und beide Nachfolger der Wurzel nur minimale Anzahl an Keys" einen Merge an der Wurzel notwendig ist, ist es in diesem Fall egal, dass die Wurzel nur einen Key hat.
- import java.noob
- Windoof-User
- Beiträge: 25
- Registriert: 2. Mär 2014 12:28
Re: Ferienübungsblatt
Ich wollte darauf hinaus dass die Umformungen die ich in den nächsten Schritten mache notwendig sind um die 300 zu löschen und daher das Ergebnis das gleiche bleibt
Re: Ferienübungsblatt
Hallo,
könnte man wenigstens für die BBaum-Aufgabe nochmal eine Musterlösung von offizieller Seite hochladen? Bei den ganzen Beiträgen hier verliert man irgendwie den Überblick. Für die Vorbereitungsaufgaben zur AI1 Klausur wurden ja auch Lösungen bereitgestellt...
Wäre cool, Grüße.
könnte man wenigstens für die BBaum-Aufgabe nochmal eine Musterlösung von offizieller Seite hochladen? Bei den ganzen Beiträgen hier verliert man irgendwie den Überblick. Für die Vorbereitungsaufgaben zur AI1 Klausur wurden ja auch Lösungen bereitgestellt...
Wäre cool, Grüße.
Re: Ferienübungsblatt
Nochmal das Video geschaut und jetzt ists klar: Beim Löschen kann der Pointer nur zum betreffenden Knoten wandern, wenn alle vorherigen mehr als m-1 elemente enthalten und beim Einfügen, wenn kein Knoten auf dem Weg zum entsprechenden Blatt voll ist.. (aber das wurde wahrscheinlich schon vorher in dieser Diskussion festgesellt
)

- import java.noob
- Windoof-User
- Beiträge: 25
- Registriert: 2. Mär 2014 12:28
Re: Ferienübungsblatt
Ja das ist richtigratatam hat geschrieben:Nochmal das Video geschaut und jetzt ists klar: Beim Löschen kann der Pointer nur zum betreffenden Knoten wandern, wenn alle vorherigen mehr als m-1 elemente enthalten und beim Einfügen, wenn kein Knoten auf dem Weg zum entsprechenden Blatt voll ist.. (aber das wurde wahrscheinlich schon vorher in dieser Diskussion festgesellt)

Re: Ferienübungsblatt
"Re: Invariante bei BTrees, Löschen und Einfügen
Ungelesener Beitragvon m_flaig » Heute 10:17
Hallo,
ja, das kann ich bestätigen. Das Einhalten der Invariante ist irrelevant. Niemand bekommt deswegen Punktabzug.
Viele Grüße,
Maximilian Flaig"
Anscheinend ist die gesamte Diskussion obsolet geworden ..
Ungelesener Beitragvon m_flaig » Heute 10:17
Hallo,
ja, das kann ich bestätigen. Das Einhalten der Invariante ist irrelevant. Niemand bekommt deswegen Punktabzug.
Viele Grüße,
Maximilian Flaig"
Anscheinend ist die gesamte Diskussion obsolet geworden ..
Re: Ferienübungsblatt
Da ich mir nicht sicher bin, ob mein Code zur Aufgabe 5 so funktionieren wird, stelle ich ihn mal hier rein. Vielleicht kann mal jemand drüberschauen? Wäre sehr dankbar. 
Abgesehen davon habe ich speziell noch zwei Fragen:
Blöde Frage, aber sehe ich das richtig, dass cmp eine Instanz eines (selbst geschriebenen) Comparators sein muss, der Comparator<T> implementiert?
Wird beim Prüfen, ob ein Key schon vorhanden ist, der "=="-Vergleich oder equals() bzw. compare() verwendet? Wenn "==" verwendet wird, könnte es ja sein, dass es zwei unterschiedliche Objekte mit gleichem Inhalt gibt. compare() würde dann 0 liefern und man müsste sich beim Weitersuchen für eine Richtung entscheiden, in der weiter gesucht wird - die ja eindeutig vorgegeben sein müsste.

Abgesehen davon habe ich speziell noch zwei Fragen:
Blöde Frage, aber sehe ich das richtig, dass cmp eine Instanz eines (selbst geschriebenen) Comparators sein muss, der Comparator<T> implementiert?
Wird beim Prüfen, ob ein Key schon vorhanden ist, der "=="-Vergleich oder equals() bzw. compare() verwendet? Wenn "==" verwendet wird, könnte es ja sein, dass es zwei unterschiedliche Objekte mit gleichem Inhalt gibt. compare() würde dann 0 liefern und man müsste sich beim Weitersuchen für eine Richtung entscheiden, in der weiter gesucht wird - die ja eindeutig vorgegeben sein müsste.
Code: Alles auswählen
public static <T> boolean find(BBaumNode<T> root, T key, Comparator<T> cmp){ //key!=null
if(root==null) return false;
int searchPos = 0;
for(int i=0; i<root.theKeys.length; i++){
if(root.theKeys[i]!=null){ //any more keys in the node?
if(cmp.compare(key,root.theKeys[i])<0){ //continue in left node
break;
}
else if(cmp.compare(key.root.theKeys[i])>0){
searchPos++; //key is not on the left side
}
else{
if(key==root.theKeys[i]) return true; //key found (is "==" correct?)
searchPos++; //key.equals(root.theKeys[i]), but not == --> continue on right side (if equal keys are always inserted on the right side)
}
}
}
}
return find(root.nodes[searchPos],key,cmp);
}
Re: Ferienübungsblatt
Dein Code war an sich von der Logik richtig, habe noch ein paar Fehler in der Grammatik verbessert.
Code: Alles auswählen
public boolean find(BNode<T> root, T key, Comparator<T> cmp){
if(root == null) return false;
BNode<T> p = root;
int searchPos = 0;
for(int i =0; i< p.theKeys.length; i++){
if(cmp.compare(key, p.theKeys[i]) <0){
break;
}
else if(cmp.compare(key, p.theKeys[i]) >0){
searchPos++;
}
else if(cmp.compare(key, p.theKeys[i])== 0){
return true;
}
}
return find(root.nodes[searchPos], key, cmp);
}
-
- Neuling
- Beiträge: 2
- Registriert: 3. Sep 2014 20:24
Re: Ferienübungsblatt
Ich schalte mich auch mal dazu. Für die Hashtabelle in Aufgabe 2 habe ich fast die gleiche Reihenfolge wie import.java.noob,
allerdings steht bei mir die 21 an Index 10, die 49 an 5 und die 33 an 12. Nach (Index|Wert) sortiert ergibt das bei mir dann
(0|52)(1|87)(2|-)(3|29)(4|17)(5|49)(6|-)(7|7)(8|73)(9|68)(10|21)(11|11)(12|33). Jemand hier der weiß welche der drei
bisher vorgeschlagenen Hashtabellen jetzt stimmt?
Danke und LG!
allerdings steht bei mir die 21 an Index 10, die 49 an 5 und die 33 an 12. Nach (Index|Wert) sortiert ergibt das bei mir dann
(0|52)(1|87)(2|-)(3|29)(4|17)(5|49)(6|-)(7|7)(8|73)(9|68)(10|21)(11|11)(12|33). Jemand hier der weiß welche der drei
bisher vorgeschlagenen Hashtabellen jetzt stimmt?

Danke und LG!
Re: Ferienübungsblatt
Meine sieht noch mal anders aus
52 21 / 29 17 87 / 7 73 68 49 11 33
Hat ein Tutor vielleicht eine Musterlösung dazu?

52 21 / 29 17 87 / 7 73 68 49 11 33
Hat ein Tutor vielleicht eine Musterlösung dazu?