当你在splay的时候你在干些什么

IMG_1306(20190407-124217).jpg

IMG_1305(20190407-124217).jpg

void rotate(int x)
{
    int y = par[x],z = par[y],k = chk(x),w = ch[x][k^1];
    ch[y][k] = w;par[w] = y;
    ch[z][chk(y)] = x;par[x] = z;
    ch[x][k^1] = y;par[y] = x;
    pushup(y);pushup(x);
}
//他改变了这棵树
void rotateback(int x)
{
    int y = ch[x][chk(x)^1],z = par[x],k = chk(y),w = ch[y][k^1];
    ch[x][k] = w;par[w] = x;
    ch[z][chk(x)] = y;par[y] = z;
    ch[y][k^1] = w;par[x] = y;
    pushup(x);pushup(y); 
    
}
//他又改了回来

//原来只要把y和x互相改一下就行了...
//chk : 子节点的方向
//ch[][2] : 存储该节点的儿子
//pushup:更新size信息

void splay(int x,int goal = 0)
{
    while(par[x] != goal)
    {
        int y = par[x],z = par[y];
        if(z != goal)
        {
            if(chk(x) == chk(y)) rotate(y);
            else rotate(x);
        }
        rotate(x);
    }
    if(!goal) root = x; 
}
//他伸展了一棵树
void splayback(int x,int goal = 0)
{
    int k = chk(x);
    while(ch[x][k] != goal)
    {
        int y = ch[x][k^1],z = ch[y][k^1];
        if(z != goal)
        {
            if(z) rotateback(x);
            rotateback(y);
        }
        rotateback(y);
    }
}
//他又伸展了回来,这段代码似乎有问题

Leave a Reply