witch doctor Geschrieben 17. Mai 2003 Teilen Geschrieben 17. Mai 2003 Hallo, wir haben in Informatik folgende Aufgabe erhalten: Die Klasse MyTreeMap enthält die Operation getNodeRec, die nach einem Knoten sucht, der einen vorgegebenen Schlüssel enthält. Diese Operation benutzt einen rekursiven Algorithmus. Programmieren Sie in der Klasse MyTreeMap die Operation private Node getNodeIt(Comparable key, Node tree), die statt eines rekursiven Algorithmus eine Schleife für die Suche nach dem Knoten verwendet. Testen Sie Ihre Operation, indem Sie in der Operation get anstatt getNodeRec die Operation getNodeIt aufrufen. Na gut, ich dachte, dass es kein Problem sein dürfte, aber irgendwie ist das bei Bäumen ein Thema für sich. Ich habe gedacht eine While-Schleife zu verwenden, aber ich weiß nciht auf was ich die beziehen soll. Ich bin echt am verzweifeln. Der Rekursive Code lautet so: private Node getNodeRec(Comparable key, Node tree) { Node result; if (tree==null) // Baum ist leer result = null; else { int cmp = key.compareTo(tree.key); if (cmp==0) // Knoten ist gefunden result = tree; else if(cmp<0) // Suchen im linken Teilbaum result = getNodeRec(key, tree.left); else // Suchen im rechten Teilbaum result = getNodeRec(key, tree.right); } return result; } Ich weiß nicht mal, wie ich anfangen soll. Trotz allem habe ich einen Ansatz, der allerdings nicht terminiert. /* * Bestimmung eines Knotens, der einen vorgegebenen Schlüssel enthält * mit Hilfe eines iterativen Algorithmus * Die Operation setzt voraus, dass key ungleich null ist. */ private Node getNodeIt(Comparable key, Node tree) { Node result; result = null; // Hier Lösung einfügen if(tree!=null) { int cmp=key.compareTo(tree.key); boolean hilfe=true; if(cmp==0) { result=tree; } else if(cmp<0) { while (hilfe) { cmp=key.compareTo(tree.left.key); } if(cmp==0) { result=tree.left; hilfe=false; } } else { hilfe=true; while(hilfe) { cmp=key.compareTo(tree.right.key); if(cmp==0) { result=tree.right; hilfe=false; } } } } return result; } Und hier der komplette Code package baum; /** * Implementierung eines binären Suchbaums * * Beachte: * Der Suchbaum ist kein ausgeglichener Baum. * Er kann durch Einfüge- und Löschoperationen zu einer * linearen Liste entarten. * * Die gespeicherten Objektreferenzen für Werte dürfen * nicht gleich null sein. * */ public class MyTreeMap { /** * Innere Klasse für die Knoten des binären Sucbaumes */ class Node { // Attribute Comparable key; // Verweis auf Schlüssel-Objekt Object value; // Verweis auf Wert-Objekt Node left; // Verweis auf linken Kindknoten Node right; // Verweis auf rechten Kindknoten // Konstruktor Node(Comparable key, Object value) { this.key = key; this.value = value; this.left = null; this.right = null; } } // Attribute (Klasse MyTreeMap) private Node root; // Verweis auf Wurzelknoten des Binärbaumes private int size; // Anzahl der Knoten des Binärbaumes // Konstruktor (Klasse MyTreeMap) /** * Erzeugung eines leeren Binärbaums */ public MyTreeMap() { this.root = null; this.size = 0; } // Operationen (Klasse MyTreeMap) /** * Bestimmung der Anzahl der Knoten im Binärbaum */ public int size() { return this.size; } /* * Bestimmung eines Knotens, der einen vorgegebenen Schlüssel enthält * mit Hilfe eines rekursiven Algorithmus * Die Operation setzt voraus, dass key ungleich null ist. */ private Node getNodeRec(Comparable key, Node tree) { Node result; if (tree==null) // Baum ist leer result = null; else { int cmp = key.compareTo(tree.key); if (cmp==0) // Knoten ist gefunden result = tree; else if(cmp<0) // Suchen im linken Teilbaum result = getNodeRec(key, tree.left); else // Suchen im rechten Teilbaum result = getNodeRec(key, tree.right); } return result; } /* * Bestimmung eines Knotens, der einen vorgegebenen Schlüssel enthält * mit Hilfe eines iterativen Algorithmus * Die Operation setzt voraus, dass key ungleich null ist. */ private Node getNodeIt(Comparable key, Node tree) { Node result; result = null; // Hier Lösung einfügen if(tree!=null) { int cmp=key.compareTo(tree.key); boolean hilfe=true; if(cmp==0) { result=tree; } else if(cmp<0) { while (hilfe) { cmp=key.compareTo(tree.left.key); } if(cmp==0) { result=tree.left; hilfe=false; } } else { hilfe=true; while(hilfe) { cmp=key.compareTo(tree.right.key); if(cmp==0) { result=tree.right; hilfe=false; } } } } return result; } /** * Bestimmung des Wertes zu einem vorgegebenen Schlüssel */ Object get(Comparable key) { Object result = null; if (key!=null) { Node p = getNodeRec(key, this.root); if (p!=null) result = p.value; } return result; } /** * Überprüfung, ob ein zu o inhaltsgleiches Objekt als Werte-Objekt * enthalten ist */ boolean containsValue(Object o) { boolean result = false; // Hier Lösung einfügen return result; } /* * Rekursives Verfahren zum Einfügen eines Paares (key,value) * in den Binärbaum mit dem Wurzelknoten tree. * Ist der Schlüssel key schon vorhanden, wird der alte * Wert durch den Wert value ersetzt. * Als Ergebnis wir ein Baum zurückgeliefert, der das * Paar (key, value) enthält. */ private Node insertNode(Comparable key, Object value, Node tree) { if (tree==null) { // Neuen Knoten erzeugen tree = new Node(key, value); this.size++; } else { int cmp = key.compareTo(tree.key); if (cmp==0) { // Alter Wert wir durch neuen Wert ersetzt tree.value = value; } else if(cmp<0) // Einfügen im linken Teilbaum tree.left = insertNode(key, value, tree.left); else // Einfügen im rechten Teilbaum tree.right = insertNode(key, value, tree.right); } return tree; } /** * Einfügen eines Paares (key,value) in den Binärbaum * Ist der Schlüssel key schon vorhanden, wird der alte * Wert durch den Wert value ersetzt. */ void put(Comparable key, Object value) { if (key!=null && value!=null) this.root = insertNode(key, value, this.root); } /* * Bestimmung des Elternknotens des symmetrischen Nachfolgers * des Knotens tree * * Der symmetrische Nachfolger eines Knotens, ist der Knoten * mit dem kleinsten Schlüssel, der größer als der Schlüssel * des Knotens tree ist. * Dieser ist der am weitesten links stehende Knoten im rechten * Teilbaum des Knotens tree. */ private Node parentSymSucc(Node tree) { Node result; result = tree; if (result.right.left!=null) { result = result.right; while (result.left.left!=null) result = result.left; } return result; } /* * Rekursives Verfahren zum Entfernen eines Knotens zu einem * vorgegebenen Schlüssel im Binärbaum mit dem Wurzelknoten tree. * Als Ergebnis wir ein Baum zurückgeliefert, der den Schlüssel * key nicht mehr enthält. */ private Node removeNode(Comparable key, Node tree) { if (tree!=null) { int cmp = key.compareTo(tree.key); if (cmp<0) // Entfernen im linken Teilbaum tree.left = removeNode(key, tree.left); else if (cmp>0) // Entfernen im rechten Teilbaum tree.right = removeNode(key, tree.right); else { // zu entfernender Knoten gefunden this.size--; if (tree.left==null) tree = tree.right; // Fall 1: siehe Skript else if (tree.right==null) tree = tree.left; // Fall 2: siehe Skript else { // Knoten besitzt zwei Kindknoten Node p = parentSymSucc(tree); if (p==tree) // Fall 3: siehe Skript { tree.key = p.right.key; tree.value = p.right.value; p.right = p.right.right; } // Fall 4: siehe Skript else { tree.key = p.left.key; tree.value = p.left.value; p.left = p.left.right; } } } } return tree; } /** * Entfernen eines Eintrags im Binärbaum zu einem vorgegebenen Schlüssel */ void remove(Comparable key) { if (key!=null) this.root = removeNode(key, this.root); } /* * Rekursives Verfahren zur Ausgabe der Paare (Schlüssel,Wert) * sortiert nach aufsteigender Reihenfolge der Schlüsseln * durch einen Inorder-Durchlauf durch den Binärbaum */ private void inorderPrint(Node tree) { if (tree!=null) { inorderPrint(tree.left); System.out.println("("+tree.key+","+tree.value+")"); inorderPrint(tree.right); } } /** * Ausgabe der Paare (Schlüssel,Wert) sortiert nach aufsteigender * Reihenfolge der Schlüssel */ void print() { System.out.println("Liste der Einträge"); System.out.println("------------------"); inorderPrint(this.root); System.out.println(); } } getNodeIt sollte dann in der get Anweisung erscheinen. Also anstatt getNodeRec jetzt getNodeIt. Allerdings funktioniert meine Idee nicht. Helft mir! Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
PerdianMG Geschrieben 17. Mai 2003 Teilen Geschrieben 17. Mai 2003 Also ich würde das ganze so probieren (ungetestet): private Node getNodeIt(Comparable key, Node tree) { Node currentNode = tree; while(currentNode != null) { int currentResult = key.compareTo(currentNode.key); if(currentResult == 0) { // Gefunden! return currentNode; } else if(currentResult < 1) { currentNode = tree.left; } else { currentNode = tree.right; } } // Kein Key hat gepasst, oder Tree war direkt am Anfang null also null zurückliefern return null; } Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
witch doctor Geschrieben 18. Mai 2003 Autor Teilen Geschrieben 18. Mai 2003 Hmm... irgendwie klappt das auch nicht. Es wird zu einer Endlossschleife. Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
PerdianMG Geschrieben 18. Mai 2003 Teilen Geschrieben 18. Mai 2003 irgendwie klappt das auch nicht. Es wird zu einer Endlossschleife. Dann ist dein Baum selber falsch implementiert. Ciao Christian Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
witch doctor Geschrieben 18. Mai 2003 Autor Teilen Geschrieben 18. Mai 2003 Ähm, der Baum ist vom Prof vorgegeben. Wir sollten das Programm lediglich ergänzen. Und der rekursive Aufruf funktioniert ja auch. Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
PerdianMG Geschrieben 18. Mai 2003 Teilen Geschrieben 18. Mai 2003 Ähm, der Baum ist vom Prof vorgegeben. Wir sollten das Programm lediglich ergänzen. Naja dann weiss ich nicht wie's laufen soll... Struktur für's rekursive ist doch die: Du schnappst die die Wurzel und hangelst dich dann die Blätter entlang, solange bist du das Blatt gefunden hast, das für dein gesuchtes Objekt stimmt. Ciao Christian Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
witch doctor Geschrieben 19. Mai 2003 Autor Teilen Geschrieben 19. Mai 2003 Ja genau. Deswwegen benutzt man die compareTo Anweisung. Wenn der Schlüssel 0 ist dann entspricht der Schlüssel der Wurzel und es wurde gefunden. Ist er kleiner als 0 dann soll er nach dem gleichen Prinzip im linken Teilbaum suchen und wenn er größer als 0 ist im rechten Teilbaum suchen. Rekursiv ist es ja klar und liegt bei Bäumen sowieso auf der Hand. Iterativ würde es so oder so niemand machen, aber es ist nun mal eine Übungsaufgabe. Meine Schwierigkeit liegt halt darin, wie ich die Schleife dort einbringe. Ein Kommilitone meinte, man müsse es vielleicht mit einem Stack lösen, aber sicher sind wir uns beide nicht. Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
PerdianMG Geschrieben 19. Mai 2003 Teilen Geschrieben 19. Mai 2003 Rekursiv ist es ja klar und liegt bei Bäumen sowieso auf der Hand. Iterativ würde es so oder so niemand machen, aber es ist nun mal eine Übungsaufgabe. Also ich habe bisher noch nie einen Baum selber komplett implementiert aber so abwegig ist mir der rekursive Ansatz gar nicht - ich würde es aus Performance-Sicht aber _immer_ iterativ machen wenn es denn möglich ist. Aber ich hab gesehen wo der Fehler steckt - sind zwei ziemlich einfache Dinge: 01 private Node getNodeIt(Comparable key, Node tree) { 02 03 Node currentNode = tree; 04 while(currentNode != null) { 05 int currentResult = key.compareTo(currentNode.key); 06 if(currentResult == 0) { 07 // Gefunden! 09 return currentNode; 10 } else if(currentResult < 0) { 11 currentNode = currentNode.left; 12 } else { 13 currentNode = currentNode.right; 14 } 15 } 16 17 return null; 18 19 } Die zwei Fehler steckten einmal in Zeile 10 (hier muss natürlich auf 0 und nicht auf 1 verglichen werden) und in den Zeilen 11 und 13, da muss ja von der aktuellen Node ausgegangen werden und nicht vom Ursprungsbaum. Ciao Christian P.S. Lass man folgenden Code laufen und dann sag mir nochmal ob du lieber die iterative oder recursive Variante nehmen würdest :-) public static void main(String[] args) { MyTreeMap treeMap = new MyTreeMap(); treeMap.put("5", "5"); treeMap.put("4", "4"); treeMap.put("3", "3"); treeMap.put("2", "2"); treeMap.put("6", "6"); treeMap.put("7", "7"); treeMap.put("8", "8"); long start = System.currentTimeMillis(); for(int i=0; i < 10000000; i++) { treeMap.getNodeRec("2", treeMap.root); } long end = System.currentTimeMillis(); System.err.println("Milliseconds for recursive run: " + (end - start)); start = System.currentTimeMillis(); for(int i=0; i < 10000000; i++) { treeMap.getNodeIt("2", treeMap.root); } end = System.currentTimeMillis(); System.err.println("Milliseconds for iterative run: " + (end - start)); } Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
witch doctor Geschrieben 19. Mai 2003 Autor Teilen Geschrieben 19. Mai 2003 Da endet es auch in einer Endlosschleife, aber ich habe inzwischen die Lösung und für interessierende möchte ich sie hier präsentieren: private Node getNodeIt(Comparable key, Node tree) { Node result; result = null; // Hier Lösung einfügen Node currentNode = tree; boolean nochwaszutun=true; while (nochwaszutun) { int cmp=key.compareTo(currentNode.key); if (cmp==0) //gefunden!! { result=currentNode; nochwaszutun=false; } else if (cmp<0) //Durchsuche links { if (currentNode.left==null) { nochwaszutun=false; } else { result=currentNode.left; nochwaszutun=false; } } else { if(currentNode.right==null) { nochwaszutun=false; } else { result=currentNode.right; nochwaszutun=false; } } } return result; } Ich habe einfach eine Hilfsvariable vom Typ Boolean benutzt, um das Abbrech-Kriterium zu bestimmen. Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
PerdianMG Geschrieben 19. Mai 2003 Teilen Geschrieben 19. Mai 2003 Da endet es auch in einer Endlosschleife Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
Empfohlene Beiträge
Dein Kommentar
Du kannst jetzt schreiben und Dich später registrieren. Wenn Du ein Konto hast, melde Dich jetzt an, um unter Deinem Benutzernamen zu schreiben.