Aktualisierung des AVL-Baumproblems

Question

Bis jetzt habe ich nur an der Implementierung der gleichen Seite AVL Tree Update gearbeitet.

Das Problem, das ich habe, ist, dass meine Anzeigefunktion explodiert, nachdem der binäre Suchbaum die AVL-Neuordnung durchläuft. Ich verschiebe die Zeiger entsprechend, aber wenn die Funktion bricht, wird ein anderes Objekt eingefügt, und ich kann nicht für das Leben von mir, es zu debuggen. jede Hilfe wäre sehr geschätzt.

AVLTree tree = new AVLTree(3)
tree.insert(2);
tree.insert(1); //causes the problem
tree.print();

Hier ist meine AVLTree-Klasse

public class AVLTree {

private boolean verboseMode = true;

private Comparable data;
private AVLTree left, right, parent;
private int rightHeight = -1, leftHeight = -1;

public AVLTree(Comparable obj){
    data = obj; left = null; right = null; parent = null;
}

private AVLTree(Comparable obj, AVLTree l, AVLTree r, AVLTree p){
    data = obj; left = l; right = r; parent = p;
}

public void insert(Comparable obj){
    int compare = obj.compareTo(data);
    if(compare != 0)
        if(compare < 0)
            if(left == null){
                left = new AVLTree(obj, null, null, this);
                // comment out for standard BST //
                left.updateHeight();            //
                left.updateBalance();           //
                // ///////////////////////////////
            } else
                left.insert(obj);
        else
            if(right == null){
                right = new AVLTree(obj, null, null, this);
                // comment out for standard BST //
                right.updateHeight();           //
                right.updateBalance();          //
                // ///////////////////////////////
            } else
                right.insert(obj);
    else
        System.err.printf("Object '%o' already in tree\n", obj);
}

public void updateHeight(){
    if(this.parent != null){
        if(this == this.parent.left)
            this.parent.leftHeight += 1;
        if(this == this.parent.right)
            this.parent.rightHeight += 1;
        this.parent.updateHeight();
    }
}

public void updateBalance(){
    if(this.parent != null){
        int diff = this.parent.leftHeight - this.parent.rightHeight;
        if(diff > 1 || diff < -1){
            if(this.parent.leftHeight > this.parent.rightHeight){
                AVLTree t0 = this.parent.parent;
                AVLTree t1 = this.parent;
                AVLTree t3 = this.parent.right;
                AVLTree t4 = this.right;
                this.right = t1;
                this.right.parent = this;
                if(t0 == null)
                    this.parent = null;
                else {
                    if(this == this.parent.left){
                        this.parent = t0;
                        this.parent.left = this;
                    } else {
                        this.parent = t0;
                        this.parent.right = this;
                    }
                }
                if(t4 == null)
                    this.right.left = null;
                else {
                    this.right.left = t4;
                    this.right.left.parent = this.right;
                }
                if(t3 == null)
                    this.right.right = null;
                else {
                    this.right.right = t3;
                    this.right.right.parent = this.right;
                }
            }               
        } else
            this.parent.updateBalance();
    }           
}       

public void print(){
    String loc = ""; print(loc);
} 
public void print(String loc){
    if(this.left != null){
        String tempLoc = loc+"0";
        left.print(tempLoc);
    }
    if(this.right != null){
        String tempLoc = loc+"1";
        right.print(tempLoc);
    }
    if(!verboseMode){
        System.out.printf("%s[%s], ", data, loc);
    } else
        System.out.printf("%s[%s] \t[%d, %d]\n\n", data, loc, leftHeight, rightHeight);         
}

}

Answer 1

Ihr Problem ist das folgende: Wenn Sie die Leitung anrufen tree.insert(1); //causes the problem Sie mischen den Baum und der oberste/Wurzelknoten wird geändert/neu angeordnet; Aber Ihr tree verweist auf die alte Wurzel, bevor der Baum neu geordnet wird. Ihr Code tut also genau das, was Sie ihm aufgetragen haben.

Sie können diese Methode in die Klasse aufnehmen:

public AVLTree getRoot() {

    if(parent != null) {
       return parent.getRoot();
    } else {
       return this;
    }
}

und erstellen Sie außerdem die folgende main()-Funktion:

  public static void main(String[] args) {     
    AVLTree tree = new AVLTree(3);
    System.out.println(tree.getRoot());
    tree.insert(2);
    System.out.println(tree.getRoot());
    tree.insert(1); //causes the problem
    System.out.println(tree.getRoot());
    tree.getRoot().print();
    tree.print();
  }

Ein Beispiel für die Ausgabe eines Laufs sieht wie folgt aus:

AVLTree@47b480
AVLTree@47b480
AVLTree@9b49e6
1[0]  [-1, -1]
3[1]  [1, -1]
2[]   [0, -1]
3[]   [1, -1] //this comes from the second call to print