Algorithmus zum vergleichen zweier Binärbäume |
25.04.2011, 12:52 | Auf diesen Beitrag antworten » | ||||||||||
John D Dorian | Algorithmus zum vergleichen zweier Binärbäume Meine Frage: Ich soll einen Algorithmus entwerfen der in O(n) testet, ob zwei Binärbäume mit n Elemente dieselben Elemente haben. Ich geh mal davon aus dass die Reihenfolge in denen die Elemente im Baum sind egal ist. Meine Ideen: Ich schaffs irgendwie nur in O(n²), denn ich würde jeden Wert des ersten Baumes mit (höchstens) allen Werten des zweiten Baumes vergleichen. Könnte mir jemand einen Hinweis geben wie man es in O(n) schafft? |
||||||||||
|
|||||||||||
25.04.2011, 14:38 | Auf diesen Beitrag antworten » | ||||||||||
3FingerbreitNougat | Zuerst solltest du prüfen ob die aktuellen Felder gleich sind. Dann, ob links und rechts alles gleich ist. Rekursion. So würde ich es machen. 3FBN |
||||||||||
25.04.2011, 14:47 | Auf diesen Beitrag antworten » | ||||||||||
Karlito | ist eine in-order traversierung nicht linear?? wenn ja: bäume in-order traversieren und liste bilden. dann vergleichen => laufzeit linear... achso, wichtig: suchbaumeigenschaft, sonst ist linear auch m.e. nicht möglich. VG, Karlito (sorry, wegen ortho, grad keine lust gehabt...) |
||||||||||
25.04.2011, 17:04 | Auf diesen Beitrag antworten » | ||||||||||
John D Dorian | also wenn ich die aktuellen felder überprüfe und dann links und rechts, also so gesehen beide Bäume gleichzeitig durchsuche, dann müssen die gleichen Werte ja an derselben Stelle im Baum sein, oder? und bei der traversierung, ist das wichtig dass es inorder ist oder könnte es theoretisch auch jede andere traversierung sein... aber da ist es doch das problem dass ich beide bäume erstmal in eine liste packen muss... meintest du mit "wichtig suchbaumeigenschaft" dass die liste die eiganschaft haben muss geordnet zu sein? weil wenn die liste nicht geordnet ist, geht das ja auch nur wenn die elemente an der gleichen stelle sind gerade beim schreiben ist mir eingefallen das wenn ich beide bäume erst in eine geordnete liste packe und sie dann vergleiche es ja dann 3n wäre und ich meine mal gehört zu haben das man den faktor davor vernachlässigen kann, es also dann O(n) ist? |
||||||||||
Anzeige | |||||||||||
|
|||||||||||
25.04.2011, 18:17 | Auf diesen Beitrag antworten » | ||||||||||
John D Dorian | sorry für Doppelpost, aber als unregistrierter User kann ich meinen Beitrag leider nicht editieren... also ich habs mal so gemacht (in java, ungetestet, da ich im moment keine lust hab ne Baum-Klasse zu schreiben)
kann man das so machen? was müsste man dann in der main-klasse aufrufen? cmp(tree1.inorder(), tree2.inorder())? |
||||||||||
25.04.2011, 19:47 | Auf diesen Beitrag antworten » | ||||||||||
Karlito | Die In-Order Traversierung sollte wichtig sein, der Baum sonst nicht geordnet durchgegangen wird. Suchbaumeigenschaft heißt, dass der Baum geordnet ist. D.h. links stehen immer die kleineren Werte als die Wurzel und rechts die größeren. Und O(3n) = O(n). Bei der Komplexitätsbetrachtung lässt man so ziemlich alles mögliche weg, was keine Rolle spielt. Auch wenn 3n, bleibt das Verhalten linear. Leider bin ich noch ni fit genug auf dem Gebiet um dir ne formale Begründung geben zu können. Deine Funktion müsste hinhauen (nach grobem überlesen). Und dein Aufruf auch. @3FBN: Sorry, dass ich mich einfach reingehängt habe VG, Karlito |
||||||||||
25.04.2011, 20:07 | Auf diesen Beitrag antworten » | ||||||||||
Karlito | Hab grad deine Funktion noch mal gelesen. Das haut so nicht hin. Du musst nen Baum übergeben und eine Liste generieren (wenn funktion nicht teil der Baum-Klasse). Das ist leider nicht so einfach wie du dir das da gemacht hast. Wenn die funktion teil des Baumes ist, brauchst du eigentlich nichts übergeben sondern nur inorder ausrufen und die Listen vergleichen. Ein Array kannst du m.E. auch nicht so einfach verwenden, da du was dynamisch wachsendes brauchst (LinkedList/ArrayList) oder du fügst die 2 Arrays für links und rechts mit deinem Wert zusammen. VG, Karlito |
||||||||||
25.04.2011, 20:29 | Auf diesen Beitrag antworten » | ||||||||||
John D Dorian | Wie meinste das mit baum übergeben... wenn ich tree1.inorder(anzahl der elemente) mach müsste das doch eig. gehen... und bei int[] a = new int[n] wird ja ein array erstellt das genug felder hat, also man muss ja eingeben wieviel man haben will, also wenn ein neues dazu kommt oder gelöscht wird (wenn du das meinst mit dynamisch wachsen) dann trägt man halt ne andere zahl ein (oder muss noch ne methode schreiben um die anzahl der elemente herauszufinden, aber das ist ja im mom nicht gefragt)
so müsste es dann aber gehen mit tree1.cmp(tree2.inorder(anzahl der elemente)), oder? wollt eig eh nur mal so schauen wie man das implementieren kann, wir müssen das glaub ich so gar nicht sondern nur sagen wie wir das machen würden und vll in Pseudo-Code hinschreiben |
||||||||||
25.04.2011, 20:34 | Auf diesen Beitrag antworten » | ||||||||||
John D Dorian | damn wie ichs blöd find nicht editieren zu können, da ich dazu neige fehler zu machen -.- meinte:
|
||||||||||
25.04.2011, 21:40 | Auf diesen Beitrag antworten » | ||||||||||
Karlito | Dein compare müsste so gehen. Bei inorder sind noch Fehler.
Aber das grobe prinzip stimmt. Bei dynamischen datentypen bräuchtest du die Anzahl nicht. Da könntest du sowas machen wie:
Is Geschmackssache... Wie sich das auf die Laufzeit auswirkt weis ich grad nicht... |
||||||||||
25.04.2011, 22:17 | Auf diesen Beitrag antworten » | ||||||||||
John D Dorian | achso ja die anzahl bei leftchild.inorder() hab ich vergessen unter rightchild.inorder(int n) dann auch einfach nochmal a[x] = data; x++; ? und data ist ja nur der wert den ich ins array einfüge und kein arrayelement aber danke schön, dass du dir soviel zeit genommen hast ^^ |
||||||||||
25.04.2011, 22:30 | Auf diesen Beitrag antworten » | ||||||||||
Karlito | leftChild.inOrder() gibt dir doch ne Liste zurück. Da es nicht genau beschrieben ist was data sein soll, bin ich davon ausgegangen, dass es der Rückgabewert von leftChild.inOrder() sein soll. Somit wäre es ja schon ein Array und du kannst es nicht einfach einem Arrayelement zuweisen... Am besten du implementierst das mal durch und Probierst es mal aus. Sollte nicht zu lange dauern...
Gerne. VG, Karlito |
||||||||||
25.04.2011, 22:57 | Auf diesen Beitrag antworten » | ||||||||||
Pedder | RWTH laesst gruessen |
||||||||||
26.04.2011, 10:53 | Auf diesen Beitrag antworten » | ||||||||||
John D Dorian | grüße zurück, hoffe wir konnten dir auch helfen pedder ^^ und karlito wie gesagt, wir müssen es ja eig. gar nicht implementieren sondern nur den algorithmus angeben wie gesagt danke nochmals für den hinweis auf inorder ^^ |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
Die Neuesten » |
|