java - AVL 树旋转中的指针

Question

我很难理解为什么下面的树旋转代码有效。如果T2指向y.left和y.left指向x，这不是使最后一个赋值x.right = T2等于x.right = x吗？指针不应该指向初始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;
}

Answer 1

对此进行推理的最好方法是把它画出来，一次一步地完成它：

在函数的开头，我们有节点 x：

   x
  /  \
 L    R
     /   \
    l1    r1

现在我们说 y = R。

  R
 /  \
L1   R1

节点 T2 = R.Left 即 l2

然后旋转：

y.left (R1.Left) = x

     R
   /   \
  x      R1
 / \
l   R
   /  \
  l1    r1

x.right = T2 (l1)

    R
   /  \
  x    r1
 / \
l   l1

我为所有尝试（尽管在 C 中）找到的一个很好的资源总是令人困惑

Answer 2

Node T2 = y.left;

这条线指向该线运行时指向T2的同一个地方。 如果更新为指向不同的对象——在这种情况下——该更改不会反映在.y.lefty.leftxT2

请注意，如果有人更改了该对象的属性，则会反映该更改。例如代码

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

然后T2.foo将反映更改为bar. 它是对未反映y.left的引用内容的更改。这是 Java 中非常普遍的事情，与整个“引用按值传递”有关。