更新AVL樹問題

截至目前，我只一直在努力實現同一側AVL樹更新。更新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);   
}

}

來源

2011-05-02 Justin

你的問題如下：當調用線 tree.insert(1); //causes the problem 你洗牌樹和頂/根節點得到改變/重新排列; 但您的tree變量在重新排列樹之前指向舊的根。所以你的代碼完全按照你所說的去做。

您可用此法類：

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

從運行的輸出樣本如下：

[email protected] 
[email protected] 
[email protected] 
1[0] [-1, -1] 
3[1] [1, -1] 
2[] [0, -1] 
3[] [1, -1] //this comes from the second call to print

來源

2011-05-11 19:30:26 zloster

更新AVL樹問題

回答

相關問題