LiveCodings: Vielwegbäume - Methode find

olibaby
Erstie
Erstie
Beiträge: 12
Registriert: 5. Mär 2017 13:59

LiveCodings: Vielwegbäume - Methode find

Beitrag von olibaby » 27. Apr 2017 12:24

Hallo Professor Weihe,

Bei Ihrer Vorstellung der Methode "find" bei Vielwegbäumen wurden Sie heute von einem Studenten darauf aufmerksam gemacht, dass Sie die Variable p nicht überschreiben wollen, sondern eine temporäre Variable q benötigen, um die Werte zwischenzuspeichern.

Wenn ich mich richtig erinnere, haben Sie das daraufhin in der zweiten for-Schleife (Iterieren durch den Baum) und in der letzten if-Abfrage (Iterieren über die Knoten ganz rechts) getan.

Ich hoffe, ich habe mich nicht allzu unverständlich ausgedrückt.

Ich habe die Methode vorhin auf beide Weisen in Java implementiert. Bei beiden Methoden wurden die gesuchten Schlüsselwerte ohne Fehler gefunden, sie arbeiteten mit gleichem Ergebnis. Daher denke ich, dass die temporäre Variable q nicht nötig ist, um durch den Baum zu iterieren.

Hier zur Verständlichkeit mein Code (ohne Comparator, da die generischen Datenstrukturen im Gegensatz zu Integern nicht so schnell zu implementieren sind):

Code: Alles auswählen


	//node ist in dem Fall root, element ist in dem Fall der gesuchte Schlüsselwert.
	public static boolean findIterVL(TreeNodeMultiway node, int element) {

		while (node != null) {

			// TreeNodeMultiway tmp = node; //Dies wäre Ihre temporäre Variable q

			for (int i = 0; i < node.numberOfKeys; i++) {
				if (element == node.theKeys[i])
					return true;
			}

			for (int i = 0; i < node.numberOfKeys; i++) {
				if (element < node.theKeys[i]) {
					node = node.theSuccessors[i]; // hier hatten Sie p(node) durch q(tmp) ersetzt
					break;
				}
			}
			if (element > node.theKeys[node.numberOfKeys - 1]) {
				node = node.theSuccessors[node.numberOfKeys];  // hier hatten Sie p(node) durch q(tmp) ersetzt
			}
			// node = tmp;
		}
		return false;

	}
Falls ich Fehler gemacht haben sollte, bin ich natürlich bereit, meine Aussagen zu revidieren.

Viele Grüße
Yves

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: LiveCodings: Vielwegbäume - Methode find

Beitrag von Prof. Karsten Weihe » 27. Apr 2017 14:50

Das Problem war doch: Wenn node (bei mir p) in der zweiten for-Schleife auf einen Nachfolger gesetzt wird, dann wird die letzte if-Abfrage mit einem falschen Knoten ausgeführt, nämlich diesem Nachfolger. Daraus wird sich doch sicher ein Gegenbeispiel konstruieren lassen :!: :?:

KW

olibaby
Erstie
Erstie
Beiträge: 12
Registriert: 5. Mär 2017 13:59

Re: LiveCodings: Vielwegbäume - Methode find

Beitrag von olibaby » 27. Apr 2017 14:57

Ah, ich fürchte, genau diesen Fall habe ich nicht bewusst getestet. Das werde ich sofort nachholen und mich danach noch mal melden.

olibaby
Erstie
Erstie
Beiträge: 12
Registriert: 5. Mär 2017 13:59

Re: LiveCodings: Vielwegbäume - Methode find

Beitrag von olibaby » 27. Apr 2017 15:56

Ich habe mich jetzt noch mal reingefuchst und behaupte, dass es keinen Unterschied macht. Ich kann nicht genau sagen, woran es liegt, aber meine Vermutung ist, dass wir garantiert auf dem richtigen Knoten stehen, wenn wir in die letzte if-Abfrage mit true hineingehen, und nicht auf seinem Nachfolger, denn dann war die if-Abfrage in der zweiten for-Schleife false und es wird nicht der Nachfolger auf p zugewiesen.

Falls Sie oder jemand anders sich in meinen Code reinarbeiten möchte, stelle ich ihn hier zur Verfügung. Das ist aber nicht zwingend nötig, um meine Aussage oben nachzuvollziehen.

Das hier ist der Code der Methode. Hier mit einigen Hilfsausgaben, damit ich verstehe, wo sich der Compiler wann befindet.

Code: Alles auswählen

	// node ist in dem Fall root, element ist in dem Fall der gesuchte
	// Schlüsselwert.
	public static boolean findIterVL(TreeNodeMultiway node, int element) {

		while (node != null) {
			
			// TreeNodeMultiway tmp = node; //Dies wäre Ihre temporäre Variable q
			
			for (int i = 0; i < node.numberOfKeys; i++) {
				System.out.println("Das geprüfte Element: " + node.theKeys[i]);
				if (element == node.theKeys[i]){
					System.out.println("Element gefunden: " + node.theKeys[i]);
					return true;
				}
			}

			for (int i = 0; i < node.numberOfKeys; i++) {
				if (element < node.theKeys[i]) {
					System.out.println("Gehe nach links");
					node = node.theSuccessors[i]; // hier hatten Sie p(node) durch q(tmp) ersetzt
					break;
				}
			}
			if (element > node.theKeys[node.numberOfKeys - 1]) {
				System.out.println("Gehe nach rechts");
				node = node.theSuccessors[node.numberOfKeys]; // hier hatten Sie p(node) durch q(tmp) ersetzt
			}
			// node = tmp;
		}
		return false;
	}
Hier ist der erstellte Baum. Es hat geholfen, ihn zu zeichnen. Er ist nicht vollständig (womit ich meine, dass nicht jeder Knoten die volle Anzahl Kinder besitzt und nicht in jedem Knoten die gleiche Anzahl Schlüsselwerte vorhanden ist), aber das sollte kein Problem für unseren Fall darstellen.

Code: Alles auswählen

		TreeNodeMultiway MBaum = new TreeNodeMultiway(new int[]{1000,2000,3000}, new TreeNodeMultiway[4], 3);
		MBaum.theSuccessors = new TreeNodeMultiway[4];
		
		MBaum.theSuccessors[0] = new TreeNodeMultiway(new int[]{100,200}, new TreeNodeMultiway[3], 2);
		MBaum.theSuccessors[0].theSuccessors[0] = new TreeNodeMultiway(new int[]{10}, new TreeNodeMultiway[2], 1);
		MBaum.theSuccessors[0].theSuccessors[1] = new TreeNodeMultiway(new int[]{110}, new TreeNodeMultiway[2], 1);
		MBaum.theSuccessors[0].theSuccessors[2] = new TreeNodeMultiway(new int[]{210}, new TreeNodeMultiway[2], 1);
		
		MBaum.theSuccessors[1] = new TreeNodeMultiway(new int[]{1100, 1200, 1300}, new TreeNodeMultiway[4], 3);
		MBaum.theSuccessors[1].theSuccessors[1] = new TreeNodeMultiway(new int[]{1110}, new TreeNodeMultiway[2], 1);
		
		MBaum.theSuccessors[2] = new TreeNodeMultiway(new int[]{2100, 2200, 2300}, new TreeNodeMultiway[4], 3);
		
		MBaum.theSuccessors[3] = new TreeNodeMultiway(new int[]{3100, 3200, 3300}, new TreeNodeMultiway[4], 3);
		MBaum.theSuccessors[3].theSuccessors[1] = new TreeNodeMultiway(new int[]{3110, 3120}, new TreeNodeMultiway[3], 2);
		MBaum.theSuccessors[3].theSuccessors[3] = new TreeNodeMultiway(new int[]{3310, 3320}, new TreeNodeMultiway[3], 2);
Das hier wäre der Aufruf aus der Main-Methode. Hier suche ich nach 3310, der rechteste Schlüsselwert im rechtesten Knoten. Der vorletzte rechte Knoten wird hierbei ebenfalls korrekt überwandert.

Code: Alles auswählen

		System.out.println(EinsTreeNodeMultiway.findIterVL(MBaum, 3310));
Das hier ist die Ausgabe: Über den Baum wird korrekt iteriert und das Element wird gefunden, ohne temporäre Variable q.

Hier kommt findIterVL
Das geprüfte Element: 1000
Das geprüfte Element: 2000
Das geprüfte Element: 3000
Gehe nach rechts
Das geprüfte Element: 3100
Das geprüfte Element: 3200
Das geprüfte Element: 3300
Gehe nach rechts
Das geprüfte Element: 3310
Element gefunden: 3310
true


Man sieht hier, dass die if-Abfrage in der zweiten for-Schleife gar nicht durchlaufen wird, weil sie nicht zu true auswertet. Woraus folgt, dass die Variable p nicht mit dem Nachfolger überschrieben werden kann, weil dies erst in der if-Abfrage in der zweiten for-Schleife geschieht, was in diesem Fall eben nicht geschieht. Das bestätigt meine erste Aussage und müsste korrekt sein.

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: LiveCodings: Vielwegbäume - Methode find

Beitrag von Prof. Karsten Weihe » 27. Apr 2017 19:27

Ich musste noch ein bisschen darüber meditieren und sehe langsam, dass der Code tatsächlich "aus Versehen" korrekt sein könnte. Es kann sein, dass node in einer Iteration zwei Knoten absteigt, nämlich einen in der Schleife und dann noch einen weiteren in der letzten if-Abfrage. Aber das wäre in der Situation, in der das passiert, durchaus korrekt.

Genial :idea: :)

KW

P.S.: Entspricht allerdings nicht gerade dem KISS-Prinzip.

Antworten

Zurück zu „Archiv“