题解 P3369 【【模板】普通平衡树】

· · 题解

普通平衡树（treap，FHQ，Splay）

—Splay详解

各位大佬打的代码也是各有各的特色，这里蒟蒻献上一篇题解；

Splay平衡树的实现主要由两部分构成：splay的旋转+splay的前驱后驱点查找

首先介绍一下平衡树的基本概念（平衡树的定义：对于任意一个节点，左儿子的值比它小，右儿子的值比它大 ）

还有就是Splay有个很暴力的地方：就是无论什么操作，都会将该点变为root，从而方便其后的询问；

x，y，z分别为三个节点（也就是我们需要交换的节点），A,B,C则分别为该树的其他节点；其中有三个关系：

1.A<x<y;
2.x<B<y;
3.x<y<C;

我们首先要将x变为y的父亲，同时y变为x的儿子；在此期间被占掉的位置更新掉，为被占掉的不便，而被占掉的位置的原节点重新连接在新的图上（仍遵循平衡树的规则进行更新）

更新后就变成了：---->

之后按相同的方式变换x与z的位置：---->

到这我们就已经了解了Splay的大概旋转方式；

但这只是其中的一种情况，几x相对于y和y相对于z都是左儿子，有儿子时也相同； 但如果不相同呢？？？（大家可以自己画画图）

不难发现，

情况1：（相同）先交换x在交换x；
情况2：（不相同）先交换y再交换x；

于是就有了代码：

void splay(int x,int goal)//即将x转至goal的儿子；
{
    while(tree[x].fa!=goal)
    {
        int y=tree[x].fa;
        int z=tree[y].fa;
        if(z!=goal)//按前面的两种情况转；
        {
            (tree[z].ch[0]==y)^(tree[y].ch[0]==x)?rotate(x):rotate(y);
        }
        rotate(x);
    }
    if(goal==0)root=x;//更新根；
}

交换函数：

就是把该变儿子的变儿子，该变爸爸的变爸爸；

主要讲解一下ki的作用：就是记录x是y的左儿子还是右儿子；而ki^2就是与其相反；

其余的的打代码时就可以画画上面的图找找规律

void rotate(int x)
{
    int y=tree[x].fa;
    int z=tree[y].fa;
    int ki=tree[y].ch[1]==x;
    tree[z].ch[tree[z].ch[1]==y]=x;
    tree[x].fa=z;
    tree[y].ch[ki]=tree[x].ch[ki^1];
    tree[tree[x].ch[ki^1]].fa=y;
    tree[x].ch[ki^1]=y;
    tree[y].fa=x;
    updata(y);updata(x);
}

插入删除函数：

应为平衡树间节点间存在差值关系，就不可能有两个节点相等，则重复情况用cnt实现；

插入：找到该点，若有，cnt++；没有，新建；

删除：若大于1，删个数；否则，清空该节点；

void make_in(int x)
{
    int now=root,fa=0;
    while(now&&tree[now].val!=x)
    {
        fa=now;
        now=tree[now].ch[x>tree[now].val];//若x>当前节点的值，向右找；否则，向左找； 
    }
    if(now)/*存在该点*/{tree[now].cnt++;}
    else//不存在；
    {
        now=++k;
        if(fa)tree[fa].ch[x>tree[fa].val]=now;//有父亲，将其儿子赋值； 
        tree[k].fa=fa;
        tree[k].val=x;
        tree[k].size=tree[k].cnt=1;
    }
    splay(now,0);
}

void del(int x)
{
    int p_fa=pre(x);
    int n_fa=net(x);
    splay(p_fa,0); 
    splay(n_fa,p_fa);//使比x小的数为根节点及左树，比他大的在右树； 
    int tmp=tree[n_fa].ch[0];
    if(tree[tmp].cnt>1)//有多个情况； 
    {
        tree[tmp].cnt--;
        splay(tmp,0);
    }
    else tree[n_fa].ch[0]=0;//只有一个； 
}

查找函数：（还是比较好理解）

比如查找第k个数，则先找比其小的，即在左儿子内，若size大于k，则进入左儿子寻找；否则，进入右儿子，找排名为（k-size）的；

接着，就是前驱后继的函数：

前驱：即比其小而最大，则到左子树中找最大数（即左子树从上到下遍历中有右儿子的，即为其前驱，break）；

后继：即比其大而最小，则到右子树中找最小数（即右子树从上到下遍历中有左儿子的，即为其后继，break）


int pre(int x)//找前驱
{
    search(x);
    int now=tree[root].ch[0];
    while(tree[now].ch[1])
    {
        now=tree[now].ch[1];
    }
    return now;
}

int net(int x)//找后继
{
    search(x);
    int now=tree[root].ch[1];
    while(tree[now].ch[0])
    {
        now=tree[now].ch[0];
    }
    return now;
}

int find(int x)//找节点
{
    int now=root;
    while(1)
    {
        if(x<=tree[tree[now].ch[0]].size)
        {
            now=tree[now].ch[0];
        }
        else
        {
            x-=(tree[tree[now].ch[0]].size+tree[now].cnt);
            if(x<=0)return now;
            else now=tree[now].ch[1];
        }
    }
}

最后，

附上AC—Code

#include<cstdio>
#include<algorithm>
using namespace std;
int n,k=0,root;
const int maxn=100000+10;
const int inf=0x7f7f7f7f;
struct node{
    int ch[2],fa,val,cnt,size;
}tree[maxn];

void updata(int x)
{
    tree[x].size=tree[tree[x].ch[0]].size+tree[tree[x].ch[1]].size+tree[x].cnt;
}

void rotate(int x)
{
    int y=tree[x].fa;
    int z=tree[y].fa;
    int ki=tree[y].ch[1]==x;
    tree[z].ch[tree[z].ch[1]==y]=x;
    tree[x].fa=z;
    tree[y].ch[ki]=tree[x].ch[ki^1];
    tree[tree[x].ch[ki^1]].fa=y;
    tree[x].ch[ki^1]=y;
    tree[y].fa=x;
    updata(y);updata(x);
}

void splay(int x,int goal)
{
    while(tree[x].fa!=goal)
    {
        int y=tree[x].fa;
        int z=tree[y].fa;
        if(z!=goal)
        {
            (tree[z].ch[0]==y)^(tree[y].ch[0]==x)?rotate(x):rotate(y);
        }
        rotate(x);
    }
    if(goal==0)root=x;
}

void make_in(int x)
{
    int now=root,fa=0;
    while(now&&tree[now].val!=x)
    {
        fa=now;
        now=tree[now].ch[x>tree[now].val];//若x>当前节点的值，向右找；否则，向左找； 
    }
    if(now)/*存在该点*/{tree[now].cnt++;}
    else//不存在；
    {
        now=++k;
        if(fa)tree[fa].ch[x>tree[fa].val]=now;//有父亲，将其儿子赋值； 
        tree[k].fa=fa;
        tree[k].val=x;
        tree[k].size=tree[k].cnt=1;
    }
    splay(now,0);
}

void search(int x)
{
    int now=root;
    if(!now)return ;
    while(tree[now].ch[x>tree[now].val]&&x!=tree[now].val)
    {
        now=tree[now].ch[x>tree[now].val];
    }//找到了； 
    splay(now,0);//旋转为根节点； 
}

int pre(int x)
{
    search(x);
    int now=tree[root].ch[0];
    while(tree[now].ch[1])
    {
        now=tree[now].ch[1];
    }
    return now;
}

int net(int x)
{
    search(x);
    int now=tree[root].ch[1];
    while(tree[now].ch[0])
    {
        now=tree[now].ch[0];
    }
    return now;
}

int find(int x)
{
    int now=root;
    while(1)
    {
        if(x<=tree[tree[now].ch[0]].size)
        {
            now=tree[now].ch[0];
        }
        else
        {
            x-=(tree[tree[now].ch[0]].size+tree[now].cnt);
            if(x<=0)return now;
            else now=tree[now].ch[1];
        }
    }
}

void del(int x)
{
    int p_fa=pre(x);
    int n_fa=net(x);
    splay(p_fa,0); 
    splay(n_fa,p_fa);//使比x小的数为根节点及左树，比他大的在右树； 
    int tmp=tree[n_fa].ch[0];
    if(tree[tmp].cnt>1)//有多个情况； 
    {
        tree[tmp].cnt--;
        splay(tmp,0);
    }
    else tree[n_fa].ch[0]=0;//只有一个； 
}

int main(){
    scanf("%d",&n);
    int opt,x;
    make_in(inf);make_in(-inf);//保证存在前驱后继； 
    for(int i=1;i<=n;++i)
    {
        scanf("%d%d",&opt,&x);
        if(opt==1)make_in(x);
        else if(opt==2)del(x);
        else if(opt==3)
        {
            search(x);//找到x旋转为根； 
            printf("%d\n",tree[tree[root].ch[0]].size);
        }
        else if(opt==4)
        {
            printf("%d\n",tree[find(x+1)].val);
        }
        else if(opt==5)
        {
            make_in(x);
            printf("%d\n",tree[pre(x)].val);
            del(x);
        }
        else if(opt==6)
        {
            make_in(x);
            printf("%d\n",tree[net(x)].val);
            del(x);
        }
    }
    return 0;


    //                                谢谢阅读，from：   Tel兼_dope 
}