java实现伸展树
中的splay(Comparable key)方法,第198行:
splay(Comparable key)
l.right = t; /* link left */ l = t; t = t.right;
不能理解l=t;前面的l.right = t不就是被覆盖掉了吗?
l=t;
l.right = t
人生最曼妙的风景,竟是内心的淡定与从容!
这里只是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
l = t
t = t.right,t原来指向b,那么现在改成指向b的右节点,即b2
t = t.right
这么一通下来后a的左节点没变依然是a1,右节点变成b,而a2已经和a断开了。相当于把b这课子树移到了a的右边。同时l和t的指向改变了,l指向b,t指向b2
l = t;看成:l = l.right;指针的移动,方便一次迭代.
这里只是l和t这两个引用在移动:
假设l原来指向节点a,a的左节点和右节点分别是a1和a2。t原来指向节点b,b的左节点和右节点分别是b1和b2
l.right = t
,l是指向a的,这个操作也就是a的右节点变成了b,l依然指向a,t依然指向bl = t
,l改成指向b,t没变也指向bt = t.right
,t原来指向b,那么现在改成指向b的右节点,即b2这么一通下来后a的左节点没变依然是a1,右节点变成b,而a2已经和a断开了。相当于把b这课子树移到了a的右边。
同时l和t的指向改变了,l指向b,t指向b2
l = t;
看成:
l = l.right;
指针的移动,方便一次迭代.