AVLTree: Rebalancing Problem

[snowblind]

Hi, ich veruch grad nen AVLTree zu implementieren, bisher klappt wohl auch soweit alles, aber jetzt bin ich ans rebalancing gekommen, und das will einfach nicht so recht. Die Rotate-Methoden scheinen richtig zu sein, jedenfall ist die binäre-Suchbaum-Eigenschaft im Baum immer gegeben, egal wieviel ich rotiere ^^

Also kann es eigentlich nur noch an der rebalance() Methode liegen. Diese wird nach dem add() aufgerufen für den neu geaddeten Knoten, aber ich hab auch eine rebalanceAll() Methode, die ALLE Knoten von unten nach oben einmal rebalanciert. Auch wenn ich diese am Schluss aufrufe, stimmt der Baum manchmal nicht. Es kann also eigentlich nur noch an der rebalance() Methode liegen, denke ich.

Das Problem ist, dass ich am Montag die Klausur dazu schreibe, und schon seit Tagen hammermässig Gas geben muss mitm üben. Und wenn ich nicht bald mal weiterkomm mit dem AVL hier, dann wird das nix gutes mehr werden :'( Also bitte, bitte, helft mir!! xD

Hier mal meine Klassen:
(Sorry falls etwas lange und unübersichtlich, programmiere grade seit langem nochmal zum ersten Mal Java)

package avl_tree_5;

public class AVLNode {

    // ////////////////////////////////
    //
    // ** Attribute **
    //
    // ////////////////////////////////

    private Object key, value;

    private AVLNode left, right, parent;

    // ////////////////////////////////
    //
    // ** Konstruktoren **
    //
    // ////////////////////////////////

    public AVLNode(Object key) throws Exception {
	this(key, key);
    }

    public AVLNode(Object key, Object value) throws Exception {
	if (key == null)
	    throw new Exception("Uebergebener Parameter Key ist NULL!");
	if (value == null)
	    throw new Exception("Uebergebener Parameter Value ist NULL!");

	this.key = key;
	this.value = value;
	this.setLeft(null);
	this.setRight(null);
    }

    // ////////////////////////////////
    //
    // ** Klassenbezogene Methoden **
    //
    // ////////////////////////////////

    public boolean isLeaf() {
	return (this.left == null && this.right == null);
    }

    public int compareTo(AVLNode n) {
	return ((Comparable) this.key).compareTo(n.getKey());
    }

    public String toString() {
	String s = "";

	// // für unterschiedlichen key/value
	// s += "(";
	// s += this.key.toString();
	// s += "|";
	// s += this.value.toString();
	// s += ")";

	s += "(" + this.key.toString() + ")";

	return s;
    }

    // ////////////////////////////////
    //
    // ** Getter / Setter **
    //
    // ////////////////////////////////

    public void setLeft(AVLNode n) throws Exception {
	this.left = n;
    }

    public void setRight(AVLNode n) throws Exception {
	this.right = n;
    }

    public Object getKey() {
	return key;
    }

    public Object getValue() {
	return value;
    }

    public AVLNode getLeft() {
	return left;
    }

    public AVLNode getRight() {
	return right;
    }

    public AVLNode getParent() {
	return parent;
    }

    public void setParent(AVLNode parent) {
	this.parent = parent;
    }

    // public Object[] getHilfe() { // nur hilfe zum debuggen!
    // Object[] arr = new Object[4];
    // arr[0] = this.toString();
    // arr[1] = this.getLeft();
    // arr[2] = this.getRight();
    // arr[3] = this.getParent();
    // return arr;
    // }
    
    public void hilfe() { // nur hilfe zum debuggen!
	
	System.out.println("---");
	System.out.println("GetHilfe: ");
	System.out.print(this.toString());
	System.out.print(" ; left: " + this.getLeft());
	System.out.print(" ; right: " + this.getRight());
	System.out.print(" ; parent: " + this.getParent());
	System.out.println("---");

    }

}

package avl_tree_5;

import java.awt.print.Printable;
import java.util.Stack;

public class AVLTree {

    // ////////////////////////////////
    //
    // ** Attribute **
    //
    // ////////////////////////////////

    public AVLNode root; // private UMAENDERN!! nur zu testzwecken

    public AVLNode nodeIt; // Node-Iterator

    private boolean found; // gefunden-boolean

    private int heigthCounter;

    private boolean avlNature;

    // ////////////////////////////////
    //
    // ** Konstruktoren **
    //
    // ////////////////////////////////

    public AVLTree() {
	root = null;
    }

    // ////////////////////////////////
    //
    // ** Klassenbezogene Methoden **
    //
    // ////////////////////////////////

    boolean debugMode = false;

    protected void debugMsg(String message) {
	if (debugMode) // boolean ob halt ausgabe ein oder aus is
	    System.out.println(this.getClass() + ": " + message);
    }

    public void add(Object key) throws Exception {

	System.out.println("\n -> Mache add(" + key + ")");

	AVLNode n = new AVLNode(key);

	if (isEmpty()) {
	    root = n;
	} else {

	    if (key.getClass() != root.getKey().getClass())
		throw new Exception("der Key des neuen Objekts hat andere "
			+ "Klasse als die anderen Keys im Baum");

	    findKey(key);

	    if (n.compareTo(nodeIt) < 1)
		nodeIt.setLeft(n);
	    else
		nodeIt.setRight(n);

	    n.setParent(nodeIt);

	    // -- ab hier die rebalancierung --

	    System.out.println("\n -> Mache Baum Rebalancieren");
	    rebalance(n);
	    System.out.println("\n -> Baum erfolgreich rebalanciert");

	    // ------------------------------
	}
	ausgabe2();
    }

    public void rebalanceAll() throws Exception { // NUR EINE TESTMETHODE!!!
	rebalanceAll(root);
    }

    public void rebalanceAll(AVLNode n) throws Exception {
	if (n.getLeft() != null)
	    rebalance(n.getLeft());
	if (n.getRight() != null)
	    rebalance(n.getRight());
	rebalance(n);
    }

    public void rebalance(AVLNode n) throws Exception {

           // das hier isn anderer versuch, kann man uebergucken, der funktioniert genau so wenig
	// int leftHeight = getHeigthNode(n.getLeft());
	// int rightHeight = getHeigthNode(n.getRight());
	// int difference = Math.abs(leftHeight - rightHeight);
	//	
	// if(difference > 1)
	// {
	// if(leftHeight > rightHeight)
	// {
	// if(getHeigthNode(n.getLeft().getLeft()) <
	// getHeigthNode(n.getLeft().getRight()))
	// {
	// AVLNode temp = n.getLeft().getRight();
	// System.out.println("Double rotate left right");
	// rol(n.getLeft());
	// ror(n);
	// return temp;
	// }
	// else
	// {
	// AVLNode temp = n.getLeft();
	// System.out.println("Single rotate right");
	// ror(n);
	// return temp;
	// }
	// }
	//		
	// else if(leftHeight < rightHeight)
	// {
	// if(getHeigthNode(n.getRight().getRight()) <
	// getHeigthNode(n.getRight().getLeft()))
	// {
	// AVLNode temp = n.getRight().getLeft();
	// System.out.println("Double rotate right left");
	// ror(n.getRight());
	// rol(n);
	// return temp;
	// }
	// else
	// {
	// AVLNode temp = n.getRight();
	// System.out.println("Single rotate left");
	// rol(n);
	// return temp;
	// }
	// }
	// }
	// return n;

	try {
	    AVLNode gf = n.getParent().getParent(); // gf = grandFather von n
	    if (!isAVLNode(gf)) { // wenn n nicht AVL -> rebalance

		if (gf.getLeft() != null) {
		    if (gf.getLeft().getLeft() == n) // 1.fall LL
			ror(findKeyNode(gf.getKey()));
		    else if (gf.getLeft().getRight() == n) // 2.fall LR
			doppelRor(findKeyNode(gf.getKey()));
		}

		if (gf.getRight() != null) {
		    if (gf.getRight().getLeft() == n) // 3.fall RL
			doppelRol(findKeyNode(gf.getKey()));
		    else if (gf.getRight().getRight() == n) // 4. fall RR
			rol(findKeyNode(gf.getKey()));
		}

	    }

	    if (n.getParent() != null) // n.vater rebalancen
		rebalance(n.getParent());

	} catch (Exception e) {
	    System.out.println(e);
	    System.out.println("fertig mit rebalance");
	    // throw (e);
	}

    }

    public boolean isEmpty() {
	return (this.root == null);
    }

    // ////////////////////////////////
    // Suchen-Methoden
    // ////////////////////////////////

    // gibt nur zurueck ob key gefunden wird
    public boolean findKey(Object key) throws Exception {

	// kann nur nach gleichen key-objekten suchen wie schon im baum
	if (key.getClass() != root.getKey().getClass())
	    throw new Exception("der Key des gesuchten Objekts hat andere "
		    + "Klasse als die anderen Keys im Baum");

	AVLNode seekedNode = new AVLNode(key);
	found = false;
	nodeIt = null;
	return (findKey(root, seekedNode));
    }

    // 
    public AVLNode findKeyNode(Object key) throws Exception {
	if (findKey(key))
	    return nodeIt;
	else
	    return null;
    }

    private boolean findKey(AVLNode n, AVLNode seekedNode) {

	if (seekedNode.compareTo(n) == 0) {
	    found = true; // wenn knoten gefunden ist nodeIt dieser
	    nodeIt = n; // wenn am blatt angekommen, ist knoten sicher nicht im
	    // baum, nodeIt ist dann der vaterknoten des neuen
	} else if (n.isLeaf()) {
	    nodeIt = n;
	} else {
	    if (seekedNode.compareTo(n) < 1) {
		if (n.getLeft() == null)
		    nodeIt = n;
		else
		    findKey(n.getLeft(), seekedNode);
	    } else { // seekedNode.compareTo(n) > 1
		if (n.getRight() == null)
		    nodeIt = n;
		else
		    findKey(n.getRight(), seekedNode);
	    }
	}
	return found;
    }

    // ////////////////////////////////
    // GetHeight-Methoden
    // ////////////////////////////////

    public int getHeigthTree() { // Gibt die Baumhoehe = maximaler Weg root-leaf
	// zurueck [OK]
	return (getHeigthNode(getRoot()));
    }

    public int getHeigthNode(AVLNode n) { // Gibt die Hoehe = maximaler Weg
	// n-leaf
	// zurueck [OK]
	if (n == null) // steht hier weil wenn in Node Klasse:
	    return -1; // Wird mit AVLNode.getHeight drauf zugegriffen,
	else { // wenn der aber null is dann null.getHeigth() -> Error
	    heigthCounter = 0;
	    getHeigth(n, 0);
	    return heigthCounter;
	}
    }

    private void getHeigth(AVLNode n, int heigth) {
	if (heigth > heigthCounter)
	    heigthCounter = heigth;

	if (n.getLeft() != null)
	    getHeigth(n.getLeft(), heigth + 1);
	if (n.getRight() != null)
	    getHeigth(n.getRight(), heigth + 1);
    }

    // ////////////////////////////////
    // AVL-Eigenschaft-Methoden
    // ////////////////////////////////

    public boolean isAVLTree() { // ob der Baum AVL Eigenschaft hat
	if (!isEmpty()) {
	    avlNature = true;
	    isAVL(root);
	    return avlNature;
	} else
	    return true;

    }

    private void isAVL(AVLNode n) {
	if (!isAVLNode(n))
	    avlNature = false;
	else {
	    if (n.getLeft() != null)
		isAVL(n.getLeft());
	    if (n.getRight() != null)
		isAVL(n.getRight());
	}
    }

    public boolean isAVLNode(AVLNode n) { // ob ein Knoten AVL Eigenschaft hat
	int a = getHeigthNode(n.getLeft());
	int b = getHeigthNode(n.getRight());

	if (a == b)
	    return true;
	else if (a + 1 == b || a == b + 1)
	    return true;
	else
	    return false;
    }

    // Direkte syso Ausgabe in inorder (=sortiert)
    public void toStringDirectOut() {
	System.out.println("");
	toStringDirectOut(root);
    }

    private void toStringDirectOut(AVLNode n) {
	if (n.getLeft() != null)
	    toStringDirectOut(n.getLeft());
	System.out.println(n.toString() + " Vater: " + n.getParent()); // das
	// +vater
	// kann
	// weg
	if (n.getRight() != null)
	    toStringDirectOut(n.getRight());
    }

    // ////////////////////////////////
    // Rotate-Methoden
    // ////////////////////////////////

    public AVLNode rol(AVLNode n) throws Exception {

	System.out.println("\n -> Mache rol(" + n + ")");

	// wichtig, sonst geht kein ROL!
	if (n == null)
	    throw new Exception(n + " ist null -> kein ROL möglich!");
	if (n.getRight() == null)
	    throw new Exception(n + " hat kein RightChild -> kein ROL möglich!");

	boolean nIsLeftChild;

	AVLNode grandParent = n.getParent();
	AVLNode kind = n.getRight();
	AVLNode innererEnkel = kind.getLeft();

	if (grandParent != null) {
	    if (grandParent.getLeft() == n) // n is linkes kind
		nIsLeftChild = true;
	    else
		// n is rechtes kind
		nIsLeftChild = false;
	}

	n.setParent(kind);
	n.setRight(innererEnkel);

	kind.setLeft(n);
	kind.setParent(null);

	if (innererEnkel != null)
	    innererEnkel.setParent(n);

	// betrachten ob n einen Vater hat:
	if (grandParent != null) {

	    kind.setParent(grandParent);

	    if (grandParent.getLeft() == n) // n is linkes kind
		grandParent.setLeft(kind);
	    else
		// n is rechtes kind
		grandParent.setRight(kind);

	}

	// System.out.println("root vorher: " + root);

	// root neu bestimmen:
	AVLNode it = n;
	while (it.getParent() != null)
	    it = it.getParent();
	root = it;

	// System.out.println("root nachher: " + root);

	ausgabe2();

	return kind; // oder return n !?!??!??!?!??! WICHTIG
    }

    public AVLNode ror(AVLNode n) throws Exception {

	System.out.println("\n -> Mache ror(" + n + ")");

	// wichtig, sonst geht kein ROL!
	if (n == null)
	    throw new Exception(n + " ist null -> kein ROR möglich!");
	if (n.getLeft() == null)
	    throw new Exception(n + " hat kein LeftChild -> kein ROR möglich!");

	boolean nIsLeftChild;

	AVLNode grandParent = n.getParent();
	AVLNode kind = n.getLeft();
	AVLNode innererEnkel = kind.getRight();

	if (grandParent != null) {
	    if (grandParent.getRight() == n) // n is linkes kind
		nIsLeftChild = true;
	    else
		// n is rechtes kind
		nIsLeftChild = false;
	}

	n.setParent(kind);
	n.setLeft(innererEnkel);

	kind.setRight(n);
	kind.setParent(null);

	if (innererEnkel != null)
	    innererEnkel.setParent(n);

	// betrachten ob n einen Vater hat:
	if (grandParent != null) {

	    kind.setParent(grandParent);

	    if (grandParent.getRight() == n) // n is linkes kind
		grandParent.setRight(kind);
	    else
		// n is rechtes kind
		grandParent.setLeft(kind);

	}

	// System.out.println("root vorher: " + root);

	// root neu bestimmen:
	AVLNode it = n;
	while (it.getParent() != null)
	    it = it.getParent();
	root = it;

	// System.out.println("root nachher: " + root);

	ausgabe2();

	return kind; // oder return n !?!??!??!?!??! WICHTIG
    }

    public void doppelRor(AVLNode n) throws Exception {
	System.out.println("\n -> Mache doppelRor(" + n + ")");
	try {
	    AVLNode temp = n.getLeft();
	    rol(temp);
	    ror(n);
	    System.out.println("\n -> doppelRor erfolgreich");
	} catch (Exception e) {
	    System.out.println("\n -> " + e);
	    System.out.println("\n -> doppelRor klappte nicht");
	}
	ausgabe2();
    }

    public void doppelRol(AVLNode n) throws Exception {
	System.out.println("\n -> Mache doppelRol(" + n + ")");
	try {
	    AVLNode temp = n.getRight();
	    ror(temp);
	    rol(n);
	    System.out.println("\n -> doppelRol erfolgreich");
	} catch (Exception e) {
	    System.out.println("\n -> " + e);
	    System.out.println("\n -> doppelRol klappte nicht");
	}
	ausgabe2();
    }

    public void getHilfeTree() {
	getHilfeTree(root);
    }

    private void getHilfeTree(AVLNode n) {
	n.hilfe();
	System.out.println(n + " is AVL: " + isAVLNode(n));
	if (n.getLeft() != null)
	    getHilfeTree(n.getLeft());
	if (n.getRight() != null)
	    getHilfeTree(n.getRight());
    }

    // ////////////////////////////////
    // Ausgabe-Methode (Matrix)
    // ////////////////////////////////

    private String[][] arr;
    private int hoch;
    private String leerFeld = "       ";

    public void ausgabe2() {

	System.out.println("\n==== Ausgabe2: Hierarchisch ====");

	// Wenn Baum leer = Hoehe -1
	if (isEmpty()) // wenn Baum leer = Hoehe -1
	    System.out.println("\n    null");

	// Wenn Baum nur root = Hoehe 0
	else if (root.getLeft() == null && root.getRight() == null)
	    System.out.println("\n    " + root);

	// Wenn Baum nur 2-3 Elemente = Hoehe 1
	else if (getHeigthTree() == 1) {

	    arr = new String[3][3];

	    for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
		    arr[i][j] = leerFeld;
		}
	    }

	    arr[0][1] = root.toString();
	    if (root.getLeft() != null && root.getRight() != null) {
		arr[1][1] = "--+--";
		arr[2][0] = "" + root.getLeft();
		arr[1][0] = "  .--";
		arr[2][2] = "" + root.getRight();
		arr[1][2] = "--.  ";
	    } else {
		if (root.getLeft() != null) {
		    arr[1][1] = "--+  ";
		    arr[2][0] = "" + root.getLeft();
		    arr[1][0] = "  .--";
		} else { // = (root.getRight() != null)
		    arr[1][1] = "  +--";
		    arr[2][2] = "" + root.getRight();
		    arr[1][2] = "--.  ";
		}

	    }

	    for (int i = 0; i < 3; i++) { // tatsaechliche ausgabe
		System.out.print("\n    ");
		for (int j = 0; j < 3; j++) {
		    System.out.print(arr[i][j]);
		}
	    }
	    System.out.println("");

	    // Wenn Baum nur mehr als 3 Elemente = Hoehe 2(+)
	} else {

	    // Array initialisieren
	    int tiefe = this.getHeigthTree();
	    int breit = (int) (Math.pow(2, (tiefe + 1))) - 1;
	    hoch = (2 * tiefe) + 1;
	    arr = new String[hoch][breit];

	    for (int i = 0; i < hoch; i++) {
		for (int j = 0; j < breit; j++) {
		    arr[i][j] = leerFeld;
		}
	    }

	    // -------- xwert initialisieren ---------
	    arr[0][(breit / 2)] = root.toString();

	    arr[1][breit / 2] = "  +  ";

	    if (root.getLeft() != null)
		xwert(root.getLeft(), (breit / 2), ((int) Math.pow(2,
			getHeigthNode(root))), 1, 0);
	    if (root.getRight() != null)
		xwert(root.getRight(), (breit / 2), ((int) Math.pow(2,
			getHeigthNode(root))), 2, 0);
	    // ---------------------------------------

	    // ------- leere Spalten wegstreichen ----
	    int ersteBeschriebeneSpalte = 0;
	    boolean boo = false;
	    ; // false wenn unbeschrieben
	    for (int i = 0; i < breit; i++) {
		for (int j = 0; j < hoch; j++) {
		    if (arr[j][i] != leerFeld)
			boo = true;
		}
		if (!boo)
		    ersteBeschriebeneSpalte++;
	    }
	    // ---------------------------------------

	    for (int i = 0; i < hoch; i++) { // tatsaechliche ausgabe
		System.out.print("\n    ");
		for (int j = ersteBeschriebeneSpalte; j < breit; j++) {
		    System.out.print(arr[i][j]);
		}
	    }
	    System.out.println("");

	}

	System.out.print("\n======== / Ausgabe2 ==========\n");

    }

    // die special funktion:
    // vater is der xwert von weiter oben,
    // richtung: 1=von rechts, 2=von links
    // nullig: ob das null is un dann weiter null nach unten geben soll
    //
    // system: kindsknoten ist um +/- (potenzDesVaters/2) verschoben
    private void xwert(AVLNode thisNode, int vater, int potenz, int richtung,
	    int ywert) {

	int ergebnis;

	if (richtung == 1)
	    ergebnis = (vater - (potenz / 2));
	else
	    ergebnis = (vater + (potenz / 2));

	// wenn thisNode von rechts angesprochen wird
	if (richtung == 1) {
	    arr[(ywert + 1)][ergebnis] = "   .---";

	    // solange bis du auf was anderes als leerFeld kommst
	    int ii = ergebnis;
	    while (arr[(ywert + 1)][ii + 1] == leerFeld) {
		ii++;
		arr[(ywert + 1)][ii] = "------";
	    }
	    // wenn thisNode von links angesprochen wird
	} else {
	    arr[(ywert + 1)][ergebnis] = "---.  ";
	    int ii = ergebnis;
	    while (arr[(ywert + 1)][ii - 1] == leerFeld) {
		ii--;
		arr[(ywert + 1)][ii] = "------";
	    }

	}

	arr[(ywert + 2)][ergebnis] = "" + thisNode; // ausgabe von thisNode

	// fuegt das + unter thisNode ein
	if (thisNode.getLeft() != null && thisNode.getRight() != null)
	    arr[(ywert + 3)][ergebnis] = "--+--";
	else if (thisNode.getLeft() != null)
	    arr[(ywert + 3)][ergebnis] = "--+  ";
	else if (thisNode.getRight() != null)
	    arr[(ywert + 3)][ergebnis] = "  +--";

	// rekursiv mit den Kindsknoten weiter wenn vorhanden
	if (thisNode.getLeft() != null)
	    xwert(thisNode.getLeft(), ergebnis, (potenz / 2), 1, (ywert + 2));
	if (thisNode.getRight() != null)
	    xwert(thisNode.getRight(), ergebnis, (potenz / 2), 2, (ywert + 2));

    }

    // ////////////////////////////////
    //
    // ** Getter / Setter **
    //
    // ////////////////////////////////

    public AVLNode getRoot() {
	return this.root;
    }

    public static void main(String[] args) throws Exception {
	AVLTreeTest.main(args);
    }

}

 

[XHelp]

Also wirklich nachzuvollziehen was da passiert ist jetzt wirklich nicht das trivialste.
Aber bist du dir sicher, dass du richtig rotierst? Für mich sehen die Kriterien für Einfach bzw. Doppelrotation falsch aus.

Du wirst es auch ggf einfacher haben, wenn du im Knoten die Balance-Werte für die Unterbäume speicherst.

Außerdem musst du ja nicht den neu eingefügten Knoten ausbalancieren, sondern eher die Eltern auf dem Weg bis zur Wurzel

P.S. Wie kommt man auf die Idee die Frage ausgerechnet im Delphi-Forum zu duplizieren? 😀

 

[JanHH]

Also so eine rebalance-All-Methode braucht man eigentlich nicht. Soweit ich mich erinner ist nach hinzufügen eines Knotens spätestens nach einer Doppelrotation wieder alles balanciert.

Was mir noch auffällt ist dass Dein Code ziemlich lang ist. Hab auch einen AVL-Baum programmiert und der ist nur ca. halb so lang, und ich bin eigentlich ziemlich verschwenderisch mit Zeilen (was den Coding-Stil angeht). Irgendwie sieht das alles zu "prozedural" aus. So ein AVL-Baum ist gedanklich nicht ganz einfach zu verstehen, aber ist (wie das bei Bäumen oft so ist) mal wieder ein Wunderwerk an Rekursion, und wenn man das so angeht dann klappts auch relativ gut.

Was ich zum Testen gemacht hab, ist, den Baum mit zahlenwerten zu füllen und in ein Panel zu malen. Und im Internet gibts diverse Seiten mit java-Applets wo man mit solchen Bäumen rumspielen kann und schön visualisiert wird, wie die Rotationen stattfinden. Damit kann man dann checken ob sich der eigene Baum auch so verhält, Schritt für Schritt, und Fehler relativ gut finden.

 

[snowblind]

Also wirklich nachzuvollziehen was da passiert ist jetzt wirklich nicht das trivialste.
Aber bist du dir sicher, dass du richtig rotierst? Für mich sehen die Kriterien für Einfach bzw. Doppelrotation falsch aus.

Ja, alles getestet, das klappt.

P.S. Wie kommt man auf die Idee die Frage ausgerechnet im Delphi-Forum zu duplizieren? 😀

Das Forum hat mir ein Kumpel empfohlen ^^ Der meinte, dort gehts nich nur um Delphi (weswegen ich dor schon öfter geschrieben hatte), sondern ich könnte mit meinem Java Problem auch dort hin gehn.


PS: Ich hab grad rausgefunden was das Problem war 😀😀 Hab nochmal per Hand debuggt (schrittweise Ausgabe aller Daten und dem Baum usw), und gesehn, dass ich zwar überall (auch in der rebalance methode) davon ausgehe, dass doppelte Werte nicht im Baum vorkommen können. NUR in der add() Methode hab ichs irgendwie total vergessen -.- Ka wie. Und damit kam die Rebalancierung dann nich zurecht und hat alles durcheinander gebracht.
Jedenfalls gehts jetzt...Juchuuu ^^

Das mit dem umständlichen Coden kann schon sein...Wie gesagt, etwas aus der Übung ^^