更新AVL树问题

Question

到目前为止，我只致力于实现同侧 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);         
}

}

Answer 1

您的问题如下：
当您拨打电话时
树.插入(1); //导致问题
您对树进行洗牌，并且顶部/根节点被更改/重新排列；
但是您的 tree 变量在树重新排列之前指向旧的根。所以你的代码完全按照你告诉它的方式去做。

您可以将此方法添加到类中：

公共 AVLTree getRoot() {

 if(parent != null) {
       返回parent.getRoot();
    } 别的 {
       返回这个；
    }
}

并创建以下 main() 函数：

 public static void main(String[] args) {     
    AVLTree 树 = new AVLTree(3);
    System.out.println(tree.getRoot());
    树.插入(2);
    System.out.println(tree.getRoot());
    树.插入(1); //导致问题的原因
    System.out.println(tree.getRoot());
    树.getRoot().print();
    树.print();
  }

运行的示例输出如下：

<前><代码>AVLTree@47b480
AVLTree@47b480
AVLTree@9b49e6
1[0] [-1, -1]
3[1] [1, -1]
2[] [0, -1]
3[] [1, -1] //这来自第二次调用 print