java - 伸展树的展开的理解

Question

java实现伸展树

中的splay(Comparable key)方法,第198行:

l.right = t;           /* link left */
l = t;
t = t.right;

不能理解l=t;前面的l.right = t不就是被覆盖掉了吗?

Answer 1

Voici juste les deux références l et t en mouvement :

1. Supposons que l pointe à l'origine vers le nœud a, et que le nœud gauche et le nœud droit de a sont respectivement a1 et a2. t pointe à l'origine vers le nœud b, et le nœud gauche et le nœud droit de b sont respectivement b1 et b2

2. l.right = t, l pointe vers a, cette opération signifie que le nœud droit de a devient b, l pointe toujours vers a, t pointe toujours vers b

3. l = t, l est modifié pour pointer vers b, t reste inchangé et pointe vers b

4. t = t.right, t pointait à l'origine vers b, puis maintenant il pointe vers le nœud droit de b, c'est-à-dire b2

Après cette passe, le nœud gauche de a n'a pas changé et est toujours a1, le nœud droit est devenu b, et a2 a été déconnecté de a. Cela équivaut à déplacer le sous-arbre de la leçon b à droite de a.
En même temps, les directions de l et t sont modifiées, l pointe vers b et t pointe vers b2

Answer 2

l = t;
est considéré comme :
l = l.right;
Le mouvement du pointeur facilite une itération.