Pointeurs dans la rotation d'arbre AVL

Question

J'ai de la difficulté à comprendre pourquoi le code de rotation de l'arborescence ci-dessous fonctionne. Si T2 points à y.left et y.left points à , est-ce que cela fait la dernière affectation x.right = T2 égale à x.right = x? Le pointeur ne doit-il pas pointer vers la position initiale 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

Node T2 = y.left; 

Cette ligne fait T2 point au même endroit y.left pointé au moment où cette ligne a été exécutée. Si y.left est mis à jour pour pointer vers un objet différent - x, dans ce cas - ce changement est et non reflété dans T2.

Rappelez-vous, si quelqu'un a changé une propriété de cet objet, que changement serait pris en compte. Par exemple. le code

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

T2.foo refléteraient alors le changement de bar. Ce sont les changements à qui sont référençant qui ne sont pas reflétés. C'est une chose assez universelle en Java, liée à l'ensemble de la chose "les références sont passées par la valeur".

Answer 2

La meilleure façon de raisonner cela est de le tirer et passer par une étape à la fois:

Au début de la fonction que nous avons Node x:

x 
/\ 
L R 
    / \ 
    l1 r1 

maintenant, nous disons y = R.

R 
/\ 
L1 R1 

nœud T2 = R.Left qui est l2

Puis la rotation:

y.left (R1.Left) = x

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

x.right = T2 (L1)

R 
/\ 
    x r1 
/\ 
l l1 

Une grande ressource que je trouve pour tous choses essais (bien que dans C) est eternally confuzzled