Java, AVL树，不能执行rotate_right

Question

我正在使用Java实现AVLTree类，并且我遇到了一些神秘的问题:

AVLTree类定义看起来像这样:(注意有一个嵌入类AVLNode)

public class AVLTree {
private AVLNode root;
private int size;
//EMBEDDED CLASS BEGINS
private static class AVLNode {
    int data;
    int height;
    AVLNode left;
    AVLNode right;
    public AVLNode(int x) {
        this.data = x;
        this.height = 1;
        this.left = null;
        this.right = null;
    }
}
//EMBEDDED CLASS ENDS
public AVLTree(){
    root=null;
    size=0;
}//blahblahblah

rotateR函数是这样的;

public AVLNode rotateR (AVLNode node) {
    if (node.left == null) {
        return node;
    }
    else {
        AVLNode temp = node.left;
        node.left = temp.right;
        temp.right = node;
        node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
        temp.height = Math.max(getHeight(temp.left), getHeight(temp.right)) + 1;
        return temp;
    }
}

作为

调用该函数时

a.root = rotateR(a.root);

一切正常。这棵树确实在旋转;然而，当我这样写的时候:

AVLNode temp = a.root.right;
temp = rotateR(temp);

子树不旋转。

我一直在寻找rotateR函数的例子，但它们看起来都和我的相似。所以我猜当参数是temp(a.p oot.right)时，该函数只是复制了temp，但没有更改原始节点。但是，这种猜测不能解释为什么当参数为a.s oot时，原始值确实发生了变化。

有谁能帮我一下吗?

Answer 1

Java不会复制对象，除非您显式地要求它这样做。它不是c++。当你赋值一个对象变量时，你实际上是在复制一个引用。

当您旋转一个节点时，需要更新父节点以指向它的新子节点。唯一的例外是当您旋转根节点时，它没有父节点。

AVLNode temp = a.root.right;
temp = rotateR(temp);
AVLNode temp = a.root.right;
a.root.right = rotateR(temp);

这两段代码做的不是同一件事。在第一个例子中，你只是重新赋值了局部变量temp。在第二种情况下，您将更新旋转节点的父节点以指向它的新子节点。

Answer 2

这应该可以正常工作。我尝试了你的方法，对我很有效。也许你打印错了，或者把它和其他旋转一起使用，出现了问题，或者你的输入树不应该旋转。请记住，您应该打印temp而不是a.root树，因为它是硬拷贝。