Ferienübungsblatt

[import java.noob]

@Sophia: Kannst du mir vllt. sagen ob diese Vorgehensweise korrekt ist?

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

[SophiaLi1]

Nach Einfügen von 60:

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

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.

Nachtrag: 50/60 90 150/180 sind Nachfolger von 75/100

[import java.noob]

kommt dann aber aufs gleiche hinaus nur dass ich die 180 früher weglassen kann, oder?

[SophiaLi1]

Was meinst du damit?

[Stan]

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?

[SophiaLi1]

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]

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

[ratatam]

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.

[ratatam]

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]

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 )

Ja das ist richtig

[ratatam]

"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 ..

[topracer]

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.

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);
}

[Jawa]

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);	
}

[Wimpernwurst]

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!

[topracer]

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?