Stackoverflow!

[Guest]

hi

ich bin gerade dabei ein prob für einen AVL Baum zu schreiebn. klappt auch soweit so gut nur leider kann ich nur ein paar zahlen einlesen und dann bekomm ich nen fehler mit name Stackoverflow.

soweit ich weiss ist das eine fehlermeldung wenn sich rekursive methoden zu oft selbstaufrufen.

die methode wo es vor kommt sieht so aus:

	public void upin(AVLknoten k){
		//falls ich in der Wurzel bin:
		if (k == Wurzel){
			//Balancewerte anpassen:(vereinfacht)
			k.b = (Tiefe(k.r) - Tiefe(k.l));
			//eventuell Rotieren um die AVL-Bedingung widerherzustellen:
			if (Math.abs(k.b) >= 2)
				rotiere(k);
			return;
		}
		
		//Balancewerte anpassen:(vereinfacht)
		k.b = (Tiefe(k.r) - Tiefe(k.l));
		
		//eventuell Rotieren um die AVL-Bedingung widerherzustellen
		if (Math.abs(k.b) >= 2){
			rotiere(k);
			k = z;
		}
		
		//rekursiver Aufruf von upin für k.v
		upin(k.v);
	}

upin(k.v); scheint der übeltäter zu sein. nur leider hab ich keinen plan wie ich die methode anders schreiben soll damit ich keinen stackoverflow mehr bekomme.

kann mir da einer helfen?

mfg
nixblik

 

[blackMamba]

wo ist denn deine Abbruchbedingung?

Wenn ich mich nicht verlesen habe, bzw keine Klammer übersehen habe, rufst du am Ende der Methode rekursiv immer wieder sich selbst auf.
Vlt solltest du das nur unter einer if-Abfrage machen, dann kannst du das ganze abbrechen, ode rmit einer while schleife oder so....

 

[Gast]

wenn ich das in eine while mache da spuckt er mir nur die ersten 4 zahlen aus...

ich dreh langsam durch. ich weiss nicht wie ich den stackoverflow wegbekommen soll

 

[Guest]

hi hier noch mal mein ganzer code zum avl Baum:

package a08;



public class AVLbaum{
	AVLknoten Wurzel;       //Zeiger auf die Wurzel des AVL-Baumes
	AVLknoten z;            //Zeiger auf den neuen Knoten,an der Stelle um die rotiert wurde
	
	public AVLbaum(){
		Wurzel = null;
	}
	
	/*Schlüssel einfügen*/
	public void einfuegen(int key){
		
		
		
		System.out.println(key + " einfuegen");
		
		//falls der Baum leer ist:
		if (Wurzel == null) {
			Wurzel = new AVLknoten(key,null,null,null,0);
//			System.out.println("1");
//			return;
			
		}
		
		//sonst beginne bei der Wurzel:
		AVLknoten k = Wurzel;
//		System.out.println("2");
		while(true){
			//Schluessel bereits im Baum enthalten:
			if (key == k.key) {
				System.out.println("Der Schluessel " + key + " ist bereits enthalten!");
				return;
			}
			
			//Schluessel einfuegen:
			if(key <= k.key){
//				System.out.println("3");
				if(k.l == null){
//					System.out.println("4");
					k.l = new AVLknoten(key,k,null,null,0);
					upin(k);
					return;
				}else
					k = k.l;
			}else{
				if(k.r == null){
//					System.out.println("5");
					k.r = new AVLknoten(key,k,null,null,0);
					upin(k);
					return;
				}else
					k = k.r;
			}
		}
//		}
	}
	
	/*Geht rekursiv bis zur Wurzel hoch, und setzt Balance-Werte, und rotiert falls nötig.*/
	public void upin(AVLknoten k){
		//falls ich in der Wurzel bin:
		
		if (k == Wurzel){
			//Balancewerte anpassen:(vereinfacht)
			k.b = (Tiefe(k.r) - Tiefe(k.l));
			//eventuell Rotieren um die AVL-Bedingung widerherzustellen:
			if (Math.abs(k.b) >= 2)
				rotiere(k);
			return;
		}
		
		//Balancewerte anpassen:(vereinfacht)
		k.b = (Tiefe(k.r) - Tiefe(k.l));
		
		//eventuell Rotieren um die AVL-Bedingung widerherzustellen
		if (Math.abs(k.b) >= 2){
			rotiere(k);
			k = z;
			return;
		}
		
		//rekursiver Aufruf von upin für k.v	
//		if(Tiefe(k) == Tiefe(Wurzel))
		upin(k.v);
		
	}
	
	/*Rotation durchführen*/
	public void rotiere(AVLknoten k){
		if ((k.b == 2) && (k.r.b == 1)){
			Linksrotation(k);
			return;
		}
		if ((k.b == 2) && (k.r.b == -1)){
			DoppelLinksrotation(k);
			return;
		}
		if ((k.b == -2) && (k.l.b == -1)){
			Rechtsrotation(k);
			return;
		}
		if ((k.b == -2) && (k.l.b == 1)){
			DoppelRechtsrotation(k);
			return;
		}
	}
	
	/*-----------------------------------------------------------------------------------
         	 v                      v
             |                      |
             k          =>          b
            /                        \
           b                          k
	-----------------------------------------------------------------------------------*/
	private void Rechtsrotation(AVLknoten k){
		System.out.println("Rechtsrotation in " + k.key);
		AVLknoten v = k.v;
		AVLknoten b = k.l;
		
		k.l = b.r;
		k.b = 0;
		b.r = k;
		b.b = 0;
		b.v = v;
		k.v = b;

		z = b;
		
		if(k == Wurzel){
			Wurzel = b;
			return;
		}
		if(v.l == k)
			v.l = b;
		else 
			v.r = b;
	}


	/*-----------------------------------------------------------------------------------
             v                      v
             |                      |
             k          =>          b
              \                    /
               b                  k
	-----------------------------------------------------------------------------------*/
	private void Linksrotation(AVLknoten k){
		System.out.println("Linksrotation in " + k.key);
		AVLknoten v = k.v;
		AVLknoten b = k.r;
	
		k.r = b.l;
		k.b = 0;
		b.v = k;
		b.l = k;
		b.b = 0;
		k.v = b;
		z = b;
		
		if(k == Wurzel){
			Wurzel = b;
			return;
		}
		if(v.l == k)
			v.l = b;
		else
			v.r = b;
	}

	/*--------------------------------------------------------------------------------
              v                      v
              |                      |
              k                      c
            /                      /   \
           b            =>        b     k
            \
             c
	--------------------------------------------------------------------------------*/
	private void DoppelRechtsrotation(AVLknoten k){
		System.out.println("DoppelRechtsrotation in " + k.key);
		AVLknoten v = k.v;
		AVLknoten b = k.l;
		AVLknoten c = b.r;

		k.l = c.r;
		k.v = c;
		k.b = 0;

		b.r = c.l;
		b.v = c;
		b.b = 0;

		c.l = b;
		c.r = k;
		c.v = v;

		z = c;
		
		if(k == Wurzel){
			Wurzel = c;
			return;
		}
		if(v.l == k)
			v.l = c;
		else
			v.r = c;
	}


	/*--------------------------------------------------------------------------------
              v                       v
              |                       |
              k                       c
               \                    /   \
                b         =>       k     b
               /
             c
	--------------------------------------------------------------------------------*/
	private void DoppelLinksrotation(AVLknoten k){
		System.out.println("DoppelLinksrotation in " + k.key);
		AVLknoten v = k.v;
		AVLknoten b = k.r;
		AVLknoten c = b.l;

		k.r = c.l;
		k.v = c;
		k.b = 0;
		
		b.l = c.r;
		b.v = c;
		b.b = 0;
	
		c.l = k;
		c.r = b;
		c.v = v;

		z = c;
		
		if(k == Wurzel){
			Wurzel = c;
			return;
		}
		if(v.l == k)
			v.l = c;
		else 
			v.r = c;
	}

	/*Tiefe des Teilbaumes wird ermittelt*/
	public int Tiefe(AVLknoten k){
		if (k == null)
			return 0;
		return 1 + (int) Math.max(Tiefe(k.l), Tiefe(k.r));
	}
}

und AVLknoten:

package a08;

public class AVLknoten{
	int key;                //Schluessel
	AVLknoten l, r, v;      //linker,-rechter Sohn,Vater
	int b;                  //Ballance
	
	public AVLknoten(int key, AVLknoten v, AVLknoten l, AVLknoten r, int b){
		this.key = key;
		this.v = v;
		this.l = l;
		this.r = r;
		this.b = b;
	}
}

wie gesagt bei mehreren zahlen kommt im stackoverflow raus.

kann mir einer helfen wie ich das wegbekomme?

mit while und if wollte das nciht so richtig klappen. bzw hab mich da wohl etwas dumm angestellt

mfg
nixblik

 

[blackMamba]

hast du dir denn mal überlegt, wie lange deine rekursive Methode upin laufen soll?
Wie hast du denn probiert einen neue rekursion abzufangen?

 

[maki]

soweit ich weiss ist das eine fehlermeldung wenn sich rekursive methoden zu oft selbstaufrufen.

Weisst du bei wlcher Rekursiontiefe der Fehler auftritt?

Es gibt einen Bug unter Windows, hatten wir erst kürzlich: http://www.java-forum.org/de/viewtopic.php?t=67488&highlight=bug

 

[Guest]

der fehler triit nach relativ kurzer zeit schon auf... also nicht sowie in dem anderen thread bei 5000


kann mir wer verraten wie ich das:

So geht's auch unter Windows:
Code:

package test;

public class RekursionsTest implements Runnable{


   public static void main(String[] args)
   throws Exception
   {
      try
      {        
         (new Thread(new RekursionsTest())).start();
      }
      catch (Throwable t)
      {
         System.out.println(t);
      }
   }


   void doSomething(int x)
   {
      System.out.println("x: " + x);
      doSomething(x + 1);
   }

   public void run() {
      doSomething(0);
   }

}

Hab ich bei ca. 1.5 Millionen manuell abgebrochen, da es funzt.




in mein programm hinbekomme?

 

[maki]

der fehler triit nach relativ kurzer zeit schon auf... also nicht sowie in dem anderen thread bei 5000

Dann liegt es an etwas anderem, zB. einer fehlerhaften Abbruchbedingung die zur Endlosschleife führt

 

[Gast]

verzweifel bin

komisch!
ich check nicht wie ich die rekursive methode anders schreiben soll...

 

[maki]

Mahc dir doch mal einfache Log-Ausgaben rein.

 

[Gast]

und Log_ausgaben sind was?

 

[Gast]

also hab ma einfach gezählt wie oft er die methode aufruft ist doch schon so a 3000 mal für knapp 23 zahlen

 

[SlaterB]

LogAusgaben heißt,
dass du in dein Programm an strategisch wichtigen Stellen Ausgaben wie
Sytem.out.println("starte fuegeEin-Operation für Wert: "+..);
Sytem.out.println("starte upin für Wert: "+..+" von yz aus" ..);
Sytem.out.println("setze Knoten x unter Knoten y);
usw einbaust,
damit du Schritt für Schritt erkennen kannst, was dein Programm wann warum wie tut,

-------

ich kann das Programm nicht testen, da keine main-Operation mit Einfügereihenfolge der Knoten bis zum Fehler oder ähnliches vorliegt

 

[Guest]

hier ist zum beipsiel meine main mit einfachen testwerten

public class TestBench {
	
	public static void main(String[] args) {
		AVLbaum baum = new AVLbaum();

		
		baum.einfuegen(2);
		baum.einfuegen(6);
		baum.einfuegen(88);
		baum.einfuegen(7);
		baum.einfuegen(9);
		baum.einfuegen(5);
		baum.einfuegen(10);
		baum.einfuegen(11);
		baum.einfuegen(12);
		baum.einfuegen(13);
		baum.einfuegen(14);
		baum.einfuegen(15);
		baum.einfuegen(16);
		baum.einfuegen(17);
		baum.einfuegen(18);
		baum.einfuegen(19);
		baum.einfuegen(20);
		baum.einfuegen(21);
		baum.einfuegen(22);
		baum.einfuegen(23);
		baum.einfuegen(24);
		baum.einfuegen(25);
		baum.einfuegen(26);
		baum.einfuegen(27);
		baum.einfuegen(28);
		
		
	}
}

vielen dank für eure mühe .
mfg

 

[SlaterB]

das ist so simpel, geht doch echt nicht dass du sowas nicht selber machst..

in AVLknoten kommt erstmal toString:

	public String toString() {
		return "me: " + key + ", v: " + (v == null ? "null" : "" + v.key);
		// bei Bedarf auch l, r usw. aber nicht deren toString() aufrufen, Rekursion..
	}

so, dann wußtest du ja schon, dass in upin die Exception kommt,
die Operation soll geradlinig von irgendwo zur Wurzel gehen,
das können ja nicht mehr als 20 Schritte sein, nicht tausende,
also eine simple Ausgabe rein:

		System.out.println("upin: " + k);
		// rekursiver Aufruf von upin für k.v
		// if(Tiefe(k) == Tiefe(Wurzel))
		upin(k.v);

schon bekommst du die Info
upin: me: 9, v: 11
upin: me: 11, v: 9
upin: me: 9, v: 11
upin: me: 11, v: 9
upin: me: 9, v: 11
upin: me: 11, v: 9
upin: me: 9, v: 11
upin: me: 11, v: 9
upin: me: 9, v: 11

klarer Fall:
der Vater von 9 ist 11,
der Vater von 11 ist 9

irgendwo wurde also falsch verlinkt,
weiß nicht ob du schon diese Erkenntnis hattest, auf diese Weise ist das jedenfalls kinderleicht in wenigen Minuten herauszufinden

nun mach mal selber weiter und schau dir alle Stellen an, an denen der Vater gesetzt wird,
evtl nur von den Knoten 9 und 11 damit es nicht so viele Ausgaben werden,

wenn ich nur grob Code wie

		b.v = k;
		b.l = k;
		b.b = 0;
		k.v = b;

in Linksrotation() sehe, dann habe ich schon schwere Zweifel, ob das korrekt ist,
b.v ist k und k.v ist wiederum b??

edit: in Rechtsrotation() ist es anders..