java - 伸展树的展开的理解
java实现伸展树
中的splay(Comparable key)方法,第198行:
l.right = t; /* link left */
l = t;
t = t.right;不能理解l=t;前面的l.right = t不就是被覆盖掉了吗?
Heim > Fragen und Antworten > Hauptteil
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
