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