Ferienübungsblatt

Moderator: AI 2

Benutzeravatar
import java.noob
Windoof-User
Windoof-User
Beiträge: 25
Registriert: 2. Mär 2014 12:28

Re: Ferienübungsblatt

Beitrag von import java.noob »

@Sophia: Kannst du mir vllt. sagen ob diese Vorgehensweise korrekt ist?
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

Benutzeravatar
SophiaLi1
Moderator
Moderator
Beiträge: 542
Registriert: 5. Jan 2014 11:48

Re: Ferienübungsblatt

Beitrag von SophiaLi1 »

import java.noob hat geschrieben:
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

Benutzeravatar
import java.noob
Windoof-User
Windoof-User
Beiträge: 25
Registriert: 2. Mär 2014 12:28

Re: Ferienübungsblatt

Beitrag von import java.noob »

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

Benutzeravatar
SophiaLi1
Moderator
Moderator
Beiträge: 542
Registriert: 5. Jan 2014 11:48

Re: Ferienübungsblatt

Beitrag von SophiaLi1 »

Was meinst du damit?

Stan
Neuling
Neuling
Beiträge: 4
Registriert: 2. Sep 2014 15:12

Re: Ferienübungsblatt

Beitrag von 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?

Benutzeravatar
SophiaLi1
Moderator
Moderator
Beiträge: 542
Registriert: 5. Jan 2014 11:48

Re: Ferienübungsblatt

Beitrag von 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.

Benutzeravatar
import java.noob
Windoof-User
Windoof-User
Beiträge: 25
Registriert: 2. Mär 2014 12:28

Re: Ferienübungsblatt

Beitrag von 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
Erstie
Erstie
Beiträge: 14
Registriert: 30. Apr 2014 16:35

Re: Ferienübungsblatt

Beitrag von 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
Erstie
Erstie
Beiträge: 14
Registriert: 30. Apr 2014 16:35

Re: Ferienübungsblatt

Beitrag von 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 :) )

Benutzeravatar
import java.noob
Windoof-User
Windoof-User
Beiträge: 25
Registriert: 2. Mär 2014 12:28

Re: Ferienübungsblatt

Beitrag von import java.noob »

ratatam 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 :) )
Ja das ist richtig ;)

ratatam
Erstie
Erstie
Beiträge: 14
Registriert: 30. Apr 2014 16:35

Re: Ferienübungsblatt

Beitrag von 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
Mausschubser
Mausschubser
Beiträge: 53
Registriert: 10. Jan 2014 19:14

Re: Ferienübungsblatt

Beitrag von 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
Neuling
Neuling
Beiträge: 3
Registriert: 3. Sep 2014 19:06

Re: Ferienübungsblatt

Beitrag von 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
Neuling
Neuling
Beiträge: 2
Registriert: 3. Sep 2014 20:24

Re: Ferienübungsblatt

Beitrag von 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? :D
Danke und LG!

topracer
Mausschubser
Mausschubser
Beiträge: 53
Registriert: 10. Jan 2014 19:14

Re: Ferienübungsblatt

Beitrag von 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?

Antworten

Zurück zu „AI 2“