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

我找到的一个很好的资源是 eternally confuzzled

Answer 2

Node T2 = y.left;

此行使 T2 指向同一位置 y.left 指向 在该行运行时 如果 y.left 更新为指向不同的对象 -- x，在本例中 -- 该更改 而不是 反映在 T2.

中

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

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

然后 T2.foo 将反映对 bar 的更改。 y.left 是 referencing 的更改未反映出来。这是 Java 中非常普遍的事情，与整个 "references are passed by value" 事情有关。

AVL 树旋转中的指针

Pointers in AVL Tree Rotation

java

avl-tree

tree-rotation