Loading...

$splay$ 学习笔记

check评论:0 条 remove_red_eye浏览量:618 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-10-15

qwq我菜死了才刚会$splay$

首先$splay$的几个数组:

f[x]:x的父亲
ch[x][0]:x的左儿子
ch[x][1]:x的右儿子
siz[x]:以x为根的子树大小
cnt[x]:当前点有几个数(可能会重复)
key[x]:当前点代表值

我们先来说说$splay$的几个操作:

  • $clear$

删除一个结点

void clear(int x)
{
    f[x]=ch[x][0]=ch[x][1]=siz[x]=cnt[x]=key[x]=0;
    return ;
}
  • $update$

更新一个点的$size$

void update(int x)
{
    if(x)
    {
        siz[x]=cnt[x];
        if(ch[x][0])
        {
            siz[x]+=siz[ch[x][0]];
        }
        if(ch[x][1])
        {
            siz[x]+=siz[ch[x][1]];
        }
    }
}
  • $get$
    找到当前节点是他父亲的哪个儿子
int get(int x)
{
    return ch[f[x]][1]==x;
}
  • $rotate$

我们先找到$x$是他的父亲的哪个儿子,我们就假设是左儿子,则其父亲$fa$就变成$x$的右儿子,$x$的右儿子就变成$fa$的左儿子,$x$就变成$fa$的父亲的儿子,我们只需记录一下然后判断方向即可

void rotate(int x)
{
    int old=f[x],oldf=f[old],which=get(x);
    ch[old][which]=ch[x][which^1];
    f[ch[old][which]]=old;
    ch[x][which^1]=old;
    f[old]=x;
    f[x]=oldf;
    if(oldf)
    {
        ch[oldf][old==ch[oldf][1]]=x;
    }
    update(old);
    update(x);
}
  • $splay$

我们用$splay$操作将点$x$旋转至根,但是要注意,如果$x$和$fa$和$fa$的父亲三点一线,即两个儿子的方向一样,我们需要先$rotate\ fa$,不然可能会退化成单旋spaly

void splay(int x)
{
    for(int fa;fa=f[x];rotate(x))
    {
        if(f[fa])
        {
            rotate(get(x)==get(fa)?fa:x);
        }
    }
    root=x;
}

接下来,我们以洛谷$P3369$为例,来写一下$splay$的几种其他操作

  • 添加一个数

我们分类讨论,如果当前整棵树为空,直接添加至$root$即可,如果不为空,我们就从$root$向下找,左小右大,如果当前节点值等于要加入的数就$cnt++$然后$update$一下救星,如果当前值所在的点为空就新建点,然后将其$splay$到根救星

void ins(int x)
{
    if(root==0)
    {
        sz++;
        clear(sz);
        cnt[sz]=siz[sz]=1;
        key[sz]=x;
        root=sz;
        return ;
    } 
    int now=root,fa=0;
    while(1)
    {
        if(key[now]==x)
        {
            cnt[now]++;
            update(now);
            update(fa);
            splay(now);
            return ;
        }
        fa=now;
        now=ch[now][key[now]<x];
        if(now==0)
        {
            sz++;
            clear(sz);
            cnt[sz]=siz[sz]=1;
            key[sz]=x;
            ch[fa][key[fa]<x]=sz;
            f[sz]=fa;
            update(fa);
            splay(sz);
            return ;
        }
    }
}
  • 找一个数的排名

我们从根往下找,如果这个数小于当前点值就往左走,否则就把答案加上左子树的$size$,如果当前点值等于这个值,就返回$ans+1$,否则答案加上当前点的$cnt$,再往右边找,为了接下来方便,如果正好找到,我们就把它$splay$到根

int find(int x)
{
    int now=root,ans=0;
    while(1)
    {
        if(x<key[now])
        {
            now=ch[now][0];
        }
        else
        {
            ans+=(ch[now][0]?siz[ch[now][0]]:0);
            if(key[now]==x)
            {
                splay(now);
                return ans+1;
            }
            ans+=cnt[now];
            now=ch[now][1];
        }
    }
}
  • 找排名第$k$的数

类似与找数的排名,不多说了

int kth(int x)
{
    int now=root;
    while(1)
    {
        if(ch[now][0]&&x<=siz[ch[now][0]])
        {
            now=ch[now][0];
        }
        else
        {
            int rank=(ch[now][0]?siz[ch[now][0]]:0)+cnt[now];
            if(x<=rank)
            {
                return key[now];
            }
            x-=rank;
            now=ch[now][1];
        }
    }
}
  • 找前驱

我们先把这个数加入进树里,就可以保证这个点在根节点处,取完$pre$再删即可

我们想到一个点的左子树里的点都比它小,而右子树都比它大,那我们从根节点的左儿子一直往右找不就是根节点的前驱了吗?

int pre()
{
    int now=ch[root][0];
    while(ch[now][1])
    {
        now=ch[now][1];
    }
    return now;
}
  • 找后继
int suc()
{
    int now=ch[root][1];
    while(ch[now][0])
    {
        now=ch[now][0];
    }
    return now;
}
  • 删除一个点

我们又来分类讨论

我们先随便$find$一下,将点值为$x$的点$splay$到根

如果根节点$size$大于$1$,直接减即可

如果根节点$size$等于$1$,我们再分三种情况

$1.$ 根结点没有左右儿子

我们直接把根节点$clear$后,$root$设置为$0$救星

$2.$ 只有一个儿子

我们把那个儿子设为根,原来的根$clear$了救星

$3.$ 有两个儿子

我们找出根的前驱,然后把他的前驱设为根,再删除原来的根就可以了

void del(int x)
{
    find(x);
    if(cnt[root]>1)
    {
        cnt[root]--;
        update(root);
        return ;
    }
    if(!ch[root][0]&&!ch[root][1])
    {
        clear(root);
        root=0;
        return ;
    }
    else if(!ch[root][0])
    {
        int old=root;
        root=ch[old][1];
        f[root]=0;
        clear(old);
        return ;
    }
    else if(!ch[root][1])
    {
        int old=root;
        root=ch[old][0];
        f[root]=0;
        clear(old);
        return ;
    }
    int qwq=pre(),old=root;
    splay(qwq);
    ch[root][1]=ch[old][1];
    f[ch[root][1]]=root;
    clear(old);
    update(root);
}

于是就这么完了qwq

关于区间翻转,会在下一篇博客里写并给出例题

普通平衡树的完整代码:

#include <bits/stdc++.h>
using namespace std;
int f[100010],ch[100010][2],siz[100010],cnt[100010],key[100010];
int sz,root;
void clear(int x)
{
    f[x]=ch[x][0]=ch[x][1]=siz[x]=cnt[x]=key[x]=0;
    return ;
}
void update(int x)
{
    if(x)
    {
        siz[x]=cnt[x];
        if(ch[x][0])
        {
            siz[x]+=siz[ch[x][0]];
        }
        if(ch[x][1])
        {
            siz[x]+=siz[ch[x][1]];
        }
    }
}
int get(int x)
{
    return ch[f[x]][1]==x;
}
void rotate(int x)
{
    int old=f[x],oldf=f[old],which=get(x);
    ch[old][which]=ch[x][which^1];
    f[ch[old][which]]=old;
    ch[x][which^1]=old;
    f[old]=x;
    f[x]=oldf;
    if(oldf)
    {
        ch[oldf][old==ch[oldf][1]]=x;
    }
    update(old);
    update(x);
}
void splay(int x)
{
    for(int fa;fa=f[x];rotate(x))
    {
        if(f[fa])
        {
            rotate(get(x)==get(fa)?fa:x);
        }
    }
    root=x;
}
void ins(int x)
{
    if(root==0)
    {
        sz++;
        clear(sz);
        cnt[sz]=siz[sz]=1;
        key[sz]=x;
        root=sz;
        return ;
    } 
    int now=root,fa=0;
    while(1)
    {
        if(key[now]==x)
        {
            cnt[now]++;
            update(now);
            update(fa);
            splay(now);
            return ;
        }
        fa=now;
        now=ch[now][key[now]<x];
        if(now==0)
        {
            sz++;
            clear(sz);
            cnt[sz]=siz[sz]=1;
            key[sz]=x;
            ch[fa][key[fa]<x]=sz;
            f[sz]=fa;
            update(fa);
            splay(sz);
            return ;
        }
    }
}
int find(int x)
{
    int now=root,ans=0;
    while(1)
    {
        if(x<key[now])
        {
            now=ch[now][0];
        }
        else
        {
            ans+=(ch[now][0]?siz[ch[now][0]]:0);
            if(key[now]==x)
            {
                splay(now);
                return ans+1;
            }
            ans+=cnt[now];
            now=ch[now][1];
        }
    }
}
int kth(int x)
{
    int now=root;
    while(1)
    {
        if(ch[now][0]&&x<=siz[ch[now][0]])
        {
            now=ch[now][0];
        }
        else
        {
            int rank=(ch[now][0]?siz[ch[now][0]]:0)+cnt[now];
            if(x<=rank)
            {
                return key[now];
            }
            x-=rank;
            now=ch[now][1];
        }
    }
}
int pre()
{
    int now=ch[root][0];
    while(ch[now][1])
    {
        now=ch[now][1];
    }
    return now;
}
int suc()
{
    int now=ch[root][1];
    while(ch[now][0])
    {
        now=ch[now][0];
    }
    return now;
}
void del(int x)
{
    find(x);
    if(cnt[root]>1)
    {
        cnt[root]--;
        update(root);
        return ;
    }
    if(!ch[root][0]&&!ch[root][1])
    {
        clear(root);
        root=0;
        return ;
    }
    else if(!ch[root][0])
    {
        int old=root;
        root=ch[old][1];
        f[root]=0;
        clear(old);
        return ;
    }
    else if(!ch[root][1])
    {
        int old=root;
        root=ch[old][0];
        f[root]=0;
        clear(old);
        return ;
    }
    int qwq=pre(),old=root;
    splay(qwq);
    ch[root][1]=ch[old][1];
    f[ch[root][1]]=root;
    clear(old);
    update(root);
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int opt,x;
        scanf("%d%d",&opt,&x);
        if(opt==1)
        {
            ins(x);
        }
        if(opt==2)
        {
            del(x);
        }
        if(opt==3)
        {
            printf("%d\n",find(x));
        }
        if(opt==4)
        {
            printf("%d\n",kth(x));
        }
        if(opt==5)
        {
            ins(x);
            printf("%d\n",key[pre()]);
            del(x);
        }
        if(opt==6)
        {
            ins(x);
            printf("%d\n",key[suc()]);
            del(x);
        }
    }
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名