AVL Tree Rotation中的指針

我無法理解爲什麼下面的樹輪代碼有效。如果T2指向y.left和y.left指向x，這是不是使最後一個指配x.right = T2等於x.right = x？指針是不是應指向最初的T2？AVL Tree Rotation中的指針

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

來源

2017-05-31 Marc Tim Thiemann

Node T2 = y.left;

該行使得T2指向同一地點y.left指出在該行運行時。如果y.left更新爲指向不同的對象 - x，在這種情況下 - 該更改是而不是反映在T2。

請注意，如果有人更改了屬性的那個對象，那麼即更改會被反映出來。例如。代碼

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

然後T2.foo將反映變化bar。這是y.left是引用沒有反映的變化。這在Java中是非常普遍的事情，涉及到整個「引用是按值傳遞」的東西。

來源

2017-05-31 23:40:07

辯解與最好的方法是把它畫出來，並通過它在一個時間步：

在函數的開始，我們有節點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中）是eternally confuzzled

來源

2017-05-31 23:38:48

AVL Tree Rotation中的指針

回答

相關問題