更新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树问题

回答

相关问题