Search code examples
javaavl-treetree-rotation

Pointers in AVL Tree Rotation


I have trouble understanding why the below tree rotation code works. If T2 points to y.left and y.left points to x, doesn't this make the last assignment x.right = T2 equal to x.right = x? Shouldn't the pointer point to the initial T2?

Node leftRotate(Node x) {
    Node y = x.right;
    Node T2 = y.left;

    // Perform rotation
    y.left = x;
    x.right = T2;

    //  Update heights
    x.height = max(height(x.left), height(x.right)) + 1;
    y.height = max(height(y.left), height(y.right)) + 1;

    // Return new root
    return y;
}

Solution

  • Node T2 = y.left;
    

    This line makes T2 point to the same place y.left pointed at the time that line was run. If y.left is updated to point to a different object -- x, in this case -- that change is not reflected in T2.

    Mind you, if someone changed a property of that object, that change would be reflected. E.g. the code

    Node T2 = y.left;
    y.left.foo = bar;
    

    then T2.foo would reflect the change to bar. It's changes to what y.left is referencing that aren't reflected. This is a pretty universal thing in Java, related to the whole "references are passed by value" thing.