Problem mit AVL Tree : Rebalancierung

[Marc.]

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)

Code:

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("---");

    }

}

Code:

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);
    }

}

Edit: Sorry, java tags scheinen hier net zu gehn, und ich find beim Editieren auch keine anderen o_O Tut mir leid...

[fkerber]

Hi!

Für Java-Code bliebe nur die Möglichkeit [code]-Tags zu verwenden.


Liebe Grüße,
Frederic

[Marc.]

Hm, 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 ^^

[Corpsman]

Passt zwar nicht direkt zum Thema,

Aber warum sollen doppelte Elemente in einem AVL-Baum nicht erlaubt sein ?

Meiner (Generischer AVL-Baum) kann das Problemlos.