关于splay的一点问题

大家都知道 ~~（好吧也许不知道）~~ splay的删除可以把一个树的前驱转到根节点，再把后继转到前驱下面，后继的左子树就一定是要被删除的那个数。比如这样（请原谅我奇怪的变量名）：

CPP

inline void sc(int x)
{
	int front=qh(x,0),back=qh(x,1);
	splay(front,0);splay(back,front);
	int a=q[back].c[0];
	if(q[a].t>1)
	{
		q[a].t--;
		splay(a,0);
	}
	else q[back].c[0]=0;
}

然后我假如先旋转后继到根节点，再旋转前驱到根节点下面，按理说前驱的右字树就是要删除的那个树，就是这样的：

CPP

inline void sc(int x)
{
	int front=qh(x,0),back=qh(x,1);
	splay(back,0);splay(front,back);
	int a=q[front].c[1];
	if(q[a].t>1)
	{
		q[a].t--;
		splay(a,0);
	}
	else q[front].c[1]=0;
}

然后这样打我就wa了，换成第一种方式就对了

不知道是为什么，调试了一下，第一种删除后那个数变成了inf，对排名没影响，第二种变成了-inf，就有影响了。

望众dalao解决一下

关于splay的一点问题

讨论操作

回复

相关推荐

关于splay的一点问题