写法为
Splay(int x,int goal)
即将x旋转为goal的儿子,当goal为0时x旋转至根节点。 如果goal不是x的祖宗的话,好像容易出问题。特别是当x和goal分别为根节点的两棵不同子树中的时候。似乎更容易出问题
想看的给两个实例,但其实好像并不重要
void Rotate(int x, bool w) //0 for Zig 1 for Zag (Same as children relationship)
{
int y = fa(x), z = fa(y), b = c(x,!w);
if(b) //y with b
fa(b) = y;
c(y,w) = b;
c(x,!w) = y, fa(y) = x; //x with y
if(z)
c(z,(y==rc(z))) = x;//z with x
fa(x) = z, Push(y), Push(x);
return;
}
void Splay(int x, int goal) //goal is 0 represents to the root
{
for(int y = fa(x), z = fa(y), xy, yz; y != goal; Rotate(x,xy), y = fa(x), z = fa(y))
if((xy=(x==rc(y))) == (yz=(y==rc(z))) && z != goal)
Rotate(y,yz);
if(!goal)
root = x;
return;
}
void splay(int rt,int to) //将当前节点旋转至指定节点
{
to = fa[to];
while(fa[rt] ^ to) //即e[rt].fa != to
{
int up = fa[rt];
if(fa[up] == to) rotate(rt); //父亲即为指定节点
else if(getid(rt) ^ getid(up)) //不在一条线上,将自己向上旋转两次
rotate(rt),rotate(rt);
else //如果你和你的祖父在一条线上,先旋转父亲,再旋转自己
rotate(up),rotate(rt);
}
}