Java, AVL tree, cannot perform rotate_right

Question

I am implementing an AVLTree class using Java, and I have met some mysterious problems:

The AVLTree class definition looks like this: (note that there is an embedded class 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

And the rotateR function is this ;

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;
    }
}

When calling this function as

a.root = rotateR(a.root);

everything is ok. The tree does rotate; However, when I wrote this:

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

The subtree doesn't rotate.

I have been searching for examples of rotateR function, but they all look similar to mine. So I guess when the parameter is temp(a.root.right), the function simply made a copy of temp, but did not change the original node. But this guess cannot explain why the original value does change when parameter is a.root.

Could anyone help me with this?

Answer 1

Java does not copy objects unless you explicitly ask it to. It is not C++. When you assign an object variable, what you're really doing is copying a reference.

When you rotate a node, you need to update the parent node to point to its new child. The only exception is when you're rotating the root node, which has no parent node.

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

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

These two snippets of code do NOT do the same thing. In the first example, you're just reassigning the local variable temp. In the second, you're updating the rotated node's parent to point to its new child.

Answer 2

This should work fine. I tried your method as is and worked for me. Maybe you are printing it wrong, or using it together with other rotations and something goes wrong, or your input tree is not supposed to rotate. Keep in mind you should be printing the temp not the a.root tree since it's a hard copy.