Zeiger in AVL Tree Rotation

Question

Ich habe Probleme zu verstehen, warum der untenstehende Baumrotationscode funktioniert. Wenn T2 auf y.left und y.left Punkte auf x zeigt, macht das nicht die letzte Zuweisung x.right = T2 gleich x.right = x? Sollte der Zeiger nicht auf T2 zeigen?

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

Node T2 = y.left; 

Diese Linie macht T2 zeigen Sie auf den gleichen Ort y.left zeigte zum Zeitpunkt der Linie wurde ausgeführt. Wenn y.left aktualisiert wird, um auf ein anderes Objekt zu zeigen - x, in diesem Fall - ist diese Änderung nicht widergespiegelt in T2.

Wohlgemerkt, wenn jemand geändert, um eine Eigenschaft dieses Objekts würde dass Änderung widerspiegeln. Z.B. der Code

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

dann würde T2.foo die Änderung bar reflektieren. Es sind Änderungen an dem y.leftReferenzieren, die nicht wiedergegeben werden. Dies ist eine ziemlich universelle Sache in Java, bezogen auf die gesamte "Referenzen sind vorbei Wert" Sache.

Answer 2

Der beste Weg, mit diesem zu Grunde ist es zu ziehen und einen Schritt nach dem anderen durchgehen:

Zu Beginn der Funktion haben wir Knoten x:

x 
/\ 
L R 
    / \ 
    l1 r1 

Jetzt sagen wir y = R.

R 
/\ 
L1 R1 

Knoten T2 = R.Left die l2 ist

Dann wird die Rotation:

y.left (R1.Left) = x

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

x.right T2 = (l1)

R 
/\ 
    x r1 
/\ 
l l1 

Eine große Ressource I für alle gefundenen Dinge versucht (wenn auch in C) ist eternally confuzzled