java - 伸展树的展开的理解

Question

java实现伸展树

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

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

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

Answer 1

ここでは、2 つの参照 l と t が動いているだけです:

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;
ポインタの移動により 1 回の反復が容易になります。