java - 伸展树的展开的理解

Question

java实现伸展树

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

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

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

Answer 1

Here are just the two references l and t moving:

1. Suppose l originally points to node a, and the left node and right node of a are a1 and a2 respectively. t originally points to node b, and the left node and right node of b are b1 and b2 respectively

2. l.right = t, l points to a, this operation means that the right node of a becomes b, l still points to a, and t still points to b

3. l = t, l is changed to point to b, t remains unchanged and points to b

4. t = t.right, t originally pointed to b, then now it points to the right node of b, that is, b2

After this pass, the left node of a has not changed and is still a1, the right node has become b, and a2 has been disconnected from a. It is equivalent to moving the subtree of lesson b to the right of a.
At the same time, the directions of l and t are changed, l points to b, and t points to b2

Answer 2

l = t;
See as:
l = l.right;
The movement of the pointer facilitates one iteration.