java - AVL Tree节点旋转导致节点消失

Question

我正在尝试用 Java 编写一个 AVL 树，并且已经在这个问题上停留了两个晚上。当运行以下代码时，肯定会发生旋转，但最终结果(例如 leftRotate)是我丢失了节点。

public AVLNode leftRotate(AVLNode node){ //receives the grandparent node
    AVLNode temp = node.right;
    node.right = temp.left;
    temp.left = node;

    return temp;    
}

public AVLNode rightRotate(AVLNode node){
    AVLNode temp = node.left;
    node.left = temp.right;
    temp.right = node;

    return temp;
}

public AVLNode rightLeftRotate(AVLNode node){
    node.right = rightRotate(node.right);
    return leftRotate(node);
}

public AVLNode leftRightRotate(AVLNode node){
    node.left = leftRotate(node.left);
    return rightRotate(node);
}

如果我将 root = temp 添加到左右旋转方法，则旋转和新显示仅在第一次旋转时成功发生，然后事情就会变得困惑。

示例:插入 4、5，然后插入 6。旋转后，temp 保留 5 作为其值 “root”，正确包含 4 和 6 作为其左子节点和右子节点的键。然而，在方法结束后，所有这些都会消失，并且我的树根的左右子节点现在为空。

我知道我错过了一些小事，但我无法理解它。

我也知道这不是我的 addNode 函数，因为当它完成添加所有节点后，生成的树无论如何都是二叉搜索树。只有当调用这些函数时我才开始丢失节点。有什么帮助吗？

Answer 1

我认为是内存管理方式的问题，而不是AVLNode temp = node.left;或 AVLNode temp = node.left; 实例化一个新的 AVLNode 并复制信息，这样就没有指向前一个对象的指针。 发生的情况是，当您执行 AVLNode temp = node.left; 时temp是指向node.left的指针，因此如果返回temp，则所有更改和旋转都会针对原始节点完成。