Splay的小小简单疑惑
  • 板块学术版
  • 楼主Remedios
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/7/11 13:48
  • 上次更新2023/11/3 10:33:43
查看原帖
Splay的小小简单疑惑
1025802
Remedios楼主2023/7/11 13:48

写法为

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); 
    }
}
2023/7/11 13:48
加载中...