java - 伸展树的展开的理解

Question

java实现伸展树

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

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

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

Answer 1

다음은 l과 t Moving에 대한 두 가지 참고 자료입니다.

1. l이 원래 노드 a를 가리키고 a의 왼쪽 노드와 오른쪽 노드가 각각 a1과 a2라고 가정합니다. t는 원래 노드 b를 가리키고, b의 왼쪽 노드와 오른쪽 노드는 각각 b1과 b2입니다

2. l.right = t, l이 a를 가리키고, 이 연산은 a의 오른쪽 노드가 b가 된다는 의미입니다. l은 여전히 ​​a를 가리키고, t는 여전히 b를 가리킵니다

3. l = t, l은 b를 가리키도록 변경되고, t는 변경되지 않고 b를 가리킵니다

4. t = t.right, t는 원래 b를 가리켰지만 이제는 b의 오른쪽 노드, 즉 b2를 가리킵니다

이 패스 이후 a의 왼쪽 노드는 변경되지 않고 여전히 a1이고 오른쪽 노드는 b가 되었으며 a2는 a와의 연결이 끊어졌습니다. 이는 학습 b의 하위 트리를 a의 오른쪽으로 이동하는 것과 같습니다.
동시에 l과 t의 방향이 바뀌면서 l은 b를, t는 b2를 가리킵니다

Answer 2

l = t;
은 다음과 같이 간주됩니다.
l = l.right;
포인터를 움직이면 한 번의 반복이 쉬워집니다.