Registrierung Kalender Mitgliederliste Teammitglieder Suche Häufig gestellte Fragen Zur Startseite

Informatiker Board » Themengebiete » Praktische Informatik » Algorithmen » Algorithmus zum vergleichen zweier Binärbäume » Hallo Gast [Anmelden|Registrieren]
Letzter Beitrag | Erster ungelesener Beitrag Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen
Neues Thema erstellen Antwort erstellen
Zum Ende der Seite springen Algorithmus zum vergleichen zweier Binärbäume
Autor
Beitrag « Vorheriges Thema | Nächstes Thema »
John D Dorian
unregistriert
Algorithmus zum vergleichen zweier Binärbäume Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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 12:52
3FingerbreitNougat
unregistriert
Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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:38
Karlito Karlito ist männlich
Kaiser


Dabei seit: 11.04.2011
Beiträge: 1.461

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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...)

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Karlito: 25.04.2011 14:49.

25.04.2011 14:47 Karlito ist offline E-Mail an Karlito senden Beiträge von Karlito suchen Nehmen Sie Karlito in Ihre Freundesliste auf
John D Dorian
unregistriert
Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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?
25.04.2011 17:04
John D Dorian
unregistriert
Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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)

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
public int[] inorder(int n){
  int[] a = new int[n];
  int x = 0;
  if(leftChild != null)
    leftChild.inorder();
    
  a[x] = data;
  x++;
  
  if(rightChild != null)
    rightChild.inorder();
    
  return a;
}

public boolean cmp(int[] a, int[] b){
  for(int x = 0; x <= a.length x++){
    if(a[x] != b[x])
      return false
  }
  return true;
}


kann man das so machen? was müsste man dann in der main-klasse aufrufen? cmp(tree1.inorder(), tree2.inorder())?
25.04.2011 18:17
Karlito Karlito ist männlich
Kaiser


Dabei seit: 11.04.2011
Beiträge: 1.461

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Karlito: 25.04.2011 19:48.

25.04.2011 19:47 Karlito ist offline E-Mail an Karlito senden Beiträge von Karlito suchen Nehmen Sie Karlito in Ihre Freundesliste auf
Karlito Karlito ist männlich
Kaiser


Dabei seit: 11.04.2011
Beiträge: 1.461

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Karlito: 25.04.2011 20:14.

25.04.2011 20:07 Karlito ist offline E-Mail an Karlito senden Beiträge von Karlito suchen Nehmen Sie Karlito in Ihre Freundesliste auf
John D Dorian
unregistriert
Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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)

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
public boolean cmp(int[] a){
  for(int x = 0; x <= a.length x++){
    if(a[x] != b[x])
      return false
  }
  return true;
}


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:29
John D Dorian
unregistriert
Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

damn wie ichs blöd find nicht editieren zu können, da ich dazu neige fehler zu machen -.-

meinte:

code:
1:
2:
3:
4:
5:
6:
7:
public boolean cmp(int[] a){
  for(int x = 0; x <= a.length x++){
    if(a[x] != this.inorder(anzahl der elemente))
      return false
  }
  return true;
}
25.04.2011 20:34
Karlito Karlito ist männlich
Kaiser


Dabei seit: 11.04.2011
Beiträge: 1.461

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

Dein compare müsste so gehen.

Bei inorder sind noch Fehler.

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
public int[] inorder(int n){
  int[] a = new int[n];
  int x = 0;
  if(leftChild != null)
    leftChild.inorder();	//Hier müsste noch mal die Anzahl rein
				//Außerdem wäre es günstig zu schreiben
				//this.leftChild, da sonst nimand weis
				//dass es ein Member von Tree sein soll
    
  a[x] = data;			//Du kannst m.E. nicht 
				//einfach einem Arrayelement 
				//ein anderes Array zuweisen
  x++;
  
  if(rightChild != null)
    rightChild.inorder();
				//Hier fehlt dann wieder das Anfügen des Arrays von rightchild
    
  return a;
}


Aber das grobe prinzip stimmt.

Bei dynamischen datentypen bräuchtest du die Anzahl nicht. Da könntest du sowas machen wie:

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
Collection result = this.leftChild().inorder();
result.add(this.value);
result.append(this.rightChild().inOrder());

return result;

//Code nicht Korrekt! Da Enden des Baumes und erstellung der Collections fehlen


Is Geschmackssache... Wie sich das auf die Laufzeit auswirkt weis ich grad nicht...

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Karlito: 25.04.2011 21:44.

25.04.2011 21:40 Karlito ist offline E-Mail an Karlito senden Beiträge von Karlito suchen Nehmen Sie Karlito in Ihre Freundesliste auf
John D Dorian
unregistriert
Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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:17
Karlito Karlito ist männlich
Kaiser


Dabei seit: 11.04.2011
Beiträge: 1.461

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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

Zitat:
aber danke schön, dass du dir soviel zeit genommen hast ^^


Gerne.

VG,

Karlito
25.04.2011 22:30 Karlito ist offline E-Mail an Karlito senden Beiträge von Karlito suchen Nehmen Sie Karlito in Ihre Freundesliste auf
Pedder
unregistriert
Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

RWTH laesst gruessen Wink
25.04.2011 22:57
John D Dorian
unregistriert
Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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 ^^
26.04.2011 10:53
Baumstruktur | Brettstruktur
Gehe zu:
Neues Thema erstellen Antwort erstellen
Informatiker Board » Themengebiete » Praktische Informatik » Algorithmen » Algorithmus zum vergleichen zweier Binärbäume