Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Einzelaufgabe 12.5 Baumarten
Einen wunderschönen Tag miteinander,
ich habe eine Frage zur Einzelaufgabe 12.5. Mittlerweile habe ich den Treechecker fertig
implementiert und auch einen grünen Haken dafür bekommen. Nach meiner Ansicht funktioniert
mein Treechecker relativ zuverlässig und dürfte auch bestimmte Sonderfälle erkennen (z.B. den leeren Baum oder
Halde mit nur gleichen Elementen).
Nun zu meiner Frage:
Bei der Methode “boolean isSearchSubTree(SimpleBinTree.TreeNode node, T min, T max)” sollen ja ein Min- und
ein Maxwert übergeben werden. Ich habe dafür jetzt nur Pseudowerte übergeben, die ich in meinen Code nicht wiederverwendet habe, weil ich den Sinn dieser beiden Parameter nicht verstanden habe.
So: sind das nur Fake-Werte, die zur Verwirrung dienen oder verbirgt sich hinter diesen ein tieferer Sinn, der bei gewissen Testfällen für das korrekte Ergebnis sorgt? D.h. kann mein Quellcode auch ohne Implementierung dieser beiden Parameter richtig sein?
Und nur so aus Interesse: gibt es für die Heapcheck-Methode eine einfachere Lösung, als sie zweimal aufzurufen (einmal mit asc = true, einmal mit asc = false) und dann im Nachhinein zu schauen, ob mindestens eine der beiden Methoden true zurückgibt?
Ich denke, eine einfachere Methode gibt es nicht. Es gibt eine Methode, bei der man die Wurzel abfragt, ob sie die Haldeneigenschaft erfüllt. Wenn ja, kann man meistens sagen, ob das dann die Eigenschaft von Maxheap oder Minheap ist. Dann kann man den passenden Wahrheitswert an die Hilfsmethode übergeben. Diese Variante sieht etwas einfacher aus, aufwandstechnisch macht das aber keinen Unterschied.
Aber stell dir mal vor, du hast den folgenden Heap:
1
1 1
1 1 1 1
1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
und noch einen
1
1 1
1 1 1 1
1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Dann weiß man zwar, dass die Wurzel die Haldeneigenschaft erfüllt, aber da die Wurzel gleich den Kindern ist, weiß man nicht, welche das ist. Für diese Gleichheit muss ein default-Fall angegeben werden und dann wird einer dieser Heaps fälschlicherweise so ausgewertet, als würde er die Haldeneigenschaft nicht erfüllen.
Zu max und min vermute ich, dass das dem schnellerem Ablauf durch dynamisches Programmieren dient. Jedenfalls habe ich beide Variablen verwendet.
1 Like
Ich hab den min und max Parameter so verstanden:
Von einem Knoten aus gesehen muss der linke Knoten kleiner sein(min) und der rechte Knoten größer(max) als der Vaterknoten selber.
Von der Wurzel aus gesehen is das kleinste Objekt unten links, und das größte Objekt unten rechts.
Du kannst die beiden Parameter also so verwenden dass du den kleinsten und den größten Wert im Baum übergibst und die Binärbaumeigenschaft is nur erfüllt, wenn jeder Wert am linken Ast und rechten Ast größer als der min-Wert ist und kleiner als der max-Wert ist (außer natürlich beim Blatt ganz links/rechts unten).
Man kann das vielleicht auch noch ganz anders angehen aber der wichtigste Unterschied von Binärbaum zur Halde ist ja dass beim Binärbaum das linke Element kleiner und das rechte Element größer ist, was bei einer Halde nicht der Fall ist.
Zuerst verwechsle bitte die Begriffe „Binärbaum“ und „binärer Suchbaum“ nicht. Ein Binärbaum muss nicht geordnet sein, es ist lediglich ein Baum, bei dem jeder Knoten maximal 2 Kinderknoten hat. Bei einem binären Suchbaum sieht die Sache anders aus.
Weiterhin ist es sinnvoll, was du sagst, min bedeutet die kleinste einfügbare Zahl, max die größte. Andererseits kannst du schon beim Elternknoten abfragen, wohin der Wert weitergereicht werden soll. Deshalb kann man in der Tat die Aufgabe auch ohne die ganzen Parameter min und max implementieren.
Was du sonst anmerkst, ist, dass die Eigenschaft des binären Suchbaums nur erfüllt ist, wenn jeder Wert am linken Teilbaum kleiner bzw. am rechten Teilbaum größer als der Wert der Wurzel. Wie sieht es aber mit gleichen Elementen aus? Evtl. wäre min und max so eine Art Möglichkeit, die Mengeneigenschaft eines Baums zu bewahren, man will also Wiederholungen vermeiden. Dann muss man wohl in der Tat die beiden Parameter an die nächsten Methoden übergeben.
Formal hast du natürlich recht, dass es aber um binäre Suchbäume handelt ist aber schon aus der Aufgabe ersichtlich 
min und max sind aber durchaus hilfreich um binäre Suchbäume von Halden abzugrenzen.
Die Mengeneigenschaft die du ansprichst ist von vornherein erfüllt, siehe Vorlesung 12-22 und 12-23: “Ein binärer Suchbaum enthält keine doppelten Einträge.”
Damit müssen die Elemente im linken Teilbaum kleiner und die Elemente im rechten Teilbaum größer als der jeweilige Vaterknoten sein.
Ganz abgesehen davon is es ja nicht die Aufgabe Wiederholungen zu vermeiden sondern einfach nur sagen zu können um welche Art von Baum es sich handelt 
Könnte jemand von euch glücklichen mit grünem Haken euren Output posten?
sbt1 is a search tree: true
sbt1 is an AVL-Tree: true
sbt1 is a heap: false
sbt2 is a search tree: false
sbt2 is an AVL-Tree: false
sbt2 is a heap: true
sbt3 is a search tree: true
sbt3 is an AVL-Tree: false
sbt3 is a heap: false
steht auch in der main Methode in den Kommentaren - wenn auch etwas kryptisch .
1 Like
Ich weiß die Aufgabe gibt “nur” 10 Punkte, aber ich hab mir zum Heap einfach mal ein paar Testfälle geschrieben, vielleicht hat ja jemand Lust, diese selbst mal auszuprobieren. Da ich in solchen Dingen allerdings immer sehr unkreativ bin hat vielleicht jemand anderes noch ein paar komplexere Testfälle, die er unbedingt teilen möchte. Dabei einfach den Inhalt der main-Methode auskommentieren und durch folgenden Code ersetzen:
TreeChecker<Integer> checker = new TreeChecker<Integer>();
SimpleBinTree<Integer> sbt = new SimpleBinTree<Integer>();
System.out.println("heap: " + checker.isHeap(sbt));
SimpleBinTree<Integer>.TreeNode root = sbt.add(34, null, true);
System.out.println("heap: " + checker.isHeap(sbt));
SimpleBinTree<Integer>.TreeNode l1 = sbt.add(5, root, true);
SimpleBinTree<Integer>.TreeNode r1 = sbt.add(21, root, false);
System.out.println("heap: " + checker.isHeap(sbt));
SimpleBinTree<Integer>.TreeNode l2 = sbt.add(2, l1, true);
SimpleBinTree<Integer>.TreeNode l3 = sbt.add(3, l1, false);
sbt.add(1, l2, false);
sbt.add(1, l2, true);
SimpleBinTree<Integer>.TreeNode r2 = sbt.add(8, r1, true);
sbt.add(13, r1, false);
System.out.println("heap: " + checker.isHeap(sbt));
SimpleBinTree<Integer>.TreeNode r3 = sbt.add(8, r2, true);
SimpleBinTree<Integer>.TreeNode l4 = sbt.add(7, r2, false);
sbt.add(8, r3, true);
sbt.add(-8, r3, false);
sbt.add(2, l4, true);
sbt.add(3, l4, false);
System.out.println("heap: " + checker.isHeap(sbt));
sbt.add(4, l3, true);
System.out.println("heap: " + checker.isHeap(sbt));
SimpleBinTree<Integer> ones = new SimpleBinTree<Integer>();
SimpleBinTree<Integer>.TreeNode one0 = ones.add(1, null, true);
SimpleBinTree<Integer>.TreeNode one1 = ones.add(1, one0, true);
SimpleBinTree<Integer>.TreeNode one4 = ones.add(1, one0, false);
SimpleBinTree<Integer>.TreeNode one2 = ones.add(1, one1, true);
SimpleBinTree<Integer>.TreeNode one3 = ones.add(1, one1, false);
SimpleBinTree<Integer>.TreeNode one5 = ones.add(1, one4, true);
SimpleBinTree<Integer>.TreeNode one6 = ones.add(1, one4, false);
ones.add(1, one2, true);
ones.add(1, one2, false);
ones.add(1, one3, true);
ones.add(1, one3, false);
ones.add(1, one5, true);
ones.add(1, one5, false);
ones.add(1, one6, true);
ones.add(1, one6, false);
System.out.println("heap: " + checker.isHeap(ones));
SimpleBinTree<Integer> zeros = new SimpleBinTree<Integer>();
SimpleBinTree<Integer>.TreeNode one01 = zeros.add(1, null, true);
SimpleBinTree<Integer>.TreeNode one11 = zeros.add(1, one01, true);
SimpleBinTree<Integer>.TreeNode one41 = zeros.add(1, one01, false);
SimpleBinTree<Integer>.TreeNode one21 = zeros.add(1, one11, true);
SimpleBinTree<Integer>.TreeNode one31 = zeros.add(1, one11, false);
SimpleBinTree<Integer>.TreeNode one51 = zeros.add(1, one41, true);
SimpleBinTree<Integer>.TreeNode one61 = zeros.add(1, one41, false);
zeros.add(0, one21, true);
zeros.add(0, one21, false);
zeros.add(0, one31, true);
zeros.add(0, one31, false);
zeros.add(0, one51, true);
zeros.add(0, one51, false);
zeros.add(0, one61, true);
zeros.add(0, one61, false);
System.out.println("heap: " + checker.isHeap(zeros));
SimpleBinTree<Integer> ones2 = new SimpleBinTree<Integer>();
SimpleBinTree<Integer>.TreeNode one02 = ones2.add(1, null, true);
SimpleBinTree<Integer>.TreeNode one12 = ones2.add(1, one02, true);
SimpleBinTree<Integer>.TreeNode one42 = ones2.add(1, one02, false);
SimpleBinTree<Integer>.TreeNode one22 = ones2.add(1, one12, true);
SimpleBinTree<Integer>.TreeNode one32 = ones2.add(1, one12, false);
SimpleBinTree<Integer>.TreeNode one52 = ones2.add(1, one42, true);
SimpleBinTree<Integer>.TreeNode one62 = ones2.add(1, one42, false);
ones2.add(1, one22, true);
ones2.add(2, one22, false);
ones2.add(3, one32, true);
ones2.add(4, one32, false);
ones2.add(5, one52, true);
ones2.add(6, one52, false);
ones2.add(7, one62, true);
ones2.add(8, one62, false);
System.out.println("heap: " + checker.isHeap(ones2));
SimpleBinTree<Integer> ones3 = new SimpleBinTree<Integer>();
SimpleBinTree<Integer>.TreeNode one03 = ones3.add(1, null, true);
SimpleBinTree<Integer>.TreeNode one13 = ones3.add(1, one03, true);
SimpleBinTree<Integer>.TreeNode one43 = ones3.add(1, one03, false);
SimpleBinTree<Integer>.TreeNode one23 = ones3.add(1, one13, true);
SimpleBinTree<Integer>.TreeNode one33 = ones3.add(1, one13, false);
SimpleBinTree<Integer>.TreeNode one53 = ones3.add(1, one43, true);
SimpleBinTree<Integer>.TreeNode one63 = ones3.add(1, one43, false);
ones3.add(1, one23, true);
ones3.add(2, one23, false);
ones3.add(3, one33, true);
ones3.add(4, one33, false);
ones3.add(5, one53, true);
ones3.add(6, one53, false);
ones3.add(7, one63, true);
ones3.add(0, one63, false);
System.out.println("heap: " + checker.isHeap(ones3));Meine Ausgabe wäre zumindest:
heap: false
heap: true
heap: true
heap: true
heap: true
heap: false
heap: true
heap: true
heap: true
heap: false/edit:
Oha, der erste Rückgabewert ist schonmal falsch. Laut Angabe erfüllt der leere Baum alle Bedingungen.
Ich habe folgende Werte bei deinem Test raus:
heap: true
heap: true
heap: true
heap: true
heap: false
heap: false
heap: false
heap: false
heap: false
heap: falseFragt sich, wer Fehler gemacht hat 
Ich habe folgendes als Ausgabe:
heap: true
heap: true
heap: true
heap: true
heap: true
heap: false
heap: true
heap: true
heap: true
heap: false
Ich habe es mal per Hand “nachgerechnet” und die Ausgabe von hjk ist die richtige. Außerdem habe ich dieselbe Ausgabe.
Habe auch dieselbe Ausgabe wie hjk. Ansonsten habe ich noch einen Testfall für die 12.6 erstellt. Da ich keine Lust habe, einen neuen Thread aufzumachen, habe ich den Test mal hierher geschoben.
public class Test {
public static void main(String[] args) {
FancyTree<Integer> fancyTree = new FancyTree<Integer>(2);
fancyTree.insertKeyInTree(17);
fancyTree.insertKeyInTree(23);
fancyTree.insertKeyInTree(21);
fancyTree.insertKeyInTree(22);
fancyTree.insertKeyInTree(2);
fancyTree.insertKeyInTree(8);
fancyTree.insertKeyInTree(9);
fancyTree.insertKeyInTree(13);
fancyTree.insertKeyInTree(18);
fancyTree.insertKeyInTree(19);
fancyTree.insertKeyInTree(20);
fancyTree.insertKeyInTree(7);
fancyTree.insertKeyInTree(6);
fancyTree.insertKeyInTree(4);
fancyTree.insertKeyInTree(1);
fancyTree.insertKeyInTree(3);
fancyTree.insertKeyInTree(5);
fancyTree.printTree();
}
}
Ausgabe:
--> 9
--> 3 6
--> 1 2
--> 4 5
--> 7 8
--> 18 21
--> 13 17
--> 19 20
--> 22 23
Ich habe in den Übungsfolien noch folgende Heap-Eigenschaft gefunden:
In den Vorlesungsfolien ist allerdings von größergleich und kleinergleich die Rede. Meine Testfälle oben haben auch explizit auf Gleichheit getestet. Ist das jetzt eigentlich richtig oder kann man nun doch gleiche Einträge ausschließen bzw. bei gleichen Einträgen mit false aus der Methode rausgehen?
Wie das in der Aufgabe gefordert ist kann ich dir leider nicht sagen, aber:
Ein Heap ist ja eigentlich eine „Prioritätswarteschlange“ mit optimierten Zugriffszeiten. Dass bei sowas gleiche Prioritäten auftauchen ist eigentlich total normal, gewöhnlich popst du ohnehin immer nur die höchste Priorität, ohne dich für deren genauen Wert zu interessieren.
Bei Suchbäumen ist das anders: Da identifizierst du meistens die Elemente über den Index, nach dem sortiert wird. Aber am Ende finden sich doch immer für beide Fälle Anwendungsszenarien…
Leute, haltet mich für blöd, aber ich bitte um Erklärung, warum Testfall 2 die AVL-Voraussetzungen nicht erfüllt.
EDIT: sry, mb, total die suchbaum-sache überlesen
Hehe, ausgezeichnet. So hab ich tatsächlich noch einen Fehler in meiner Implementierung finden können.
/edit: hab meinen Testfall mal in den entsprechenden Thread verschoben.
min, max
hallo, warum braucht man genau die Parameter min, max in der Methode isSearchSubTree?
Weil man nicht alleine durch das Betrachten der direkten Nachfolger eines Knotens K entscheiden kann, ob es sich bei dem Teilbaum, welcher bei K beginnt, um einen Suchbaum handelt.
Servus,
wenn ein Baum leer ist oder die Nachfolger leer sind(also null-Werte haben), ist der Baum dann automatisch den 3 Arten zugehörig?