java - 伸展树的展开的理解
java实现伸展树
中的splay(Comparable key)方法,第198行:
l.right = t; /* link left */
l = t;
t = t.right;不能理解l=t;前面的l.right = t不就是被覆盖掉了吗?
java实现伸展树
中的splay(Comparable key)方法,第198行:
l.right = t; /* link left */
l = t;
t = t.right;不能理解l=t;前面的l.right = t不就是被覆盖掉了吗?
ringa_lee2017-04-18 09:53:27
這裡只是l和t這兩個引用在移動：
假設l原來指向節點a，a的左節點和右節點分別是a1和a2。 t原來指向節點b，b的左節點和右節點分別是b1和b2
l.right = t，l是指向a的，這個操作也就是a的右節點變成了b，l依然指向a，t依然指向b
l = t，l改成指向b，t沒變也指向b
t = t.right，t原來指向b，那麼現在改成指向b的右節點，即b2
這麼一通下來後a的左節點沒變依然是a1，右節點變成b，而a2已經和a斷開了。相當於把b這課子樹移到了a的右邊。
同時l和t的指向改變了，l指向b，t指向b2
