2

今のところ、同じ側の AVL ツリーの更新の実装のみに取り組んでいます。

私が得ている問題は、バイナリ検索ツリーが AVL の並べ替えを通過した後、表示機能が爆発することです。それに応じてポインターを移動しますが、関数が壊れると別のオブジェクトが挿入され、一生デバッグできません。どんな助けでも大歓迎です。

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

ここに私のAVLTreeクラスがあります

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

}

4

1 に答える 1

0

問題は次のとおりです。行を呼び出すと tree.insert(1); //causes the problem 、ツリーがシャッフルされ、最上位/ルート ノードが変更/再配置されます。ただし、tree変数は、ツリーが再配置される前の古いルートを指しています。したがって、あなたのコードは、あなたが指示したことを正確に実行しています。

クラスに対してこのメ​​ソッドを実行できます。

public AVLTree getRoot() {

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

また、次の main() 関数を作成します。

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

実行からのサンプル出力は次のとおりです。 

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
于 2011-05-11T19:30:26.630 に答える