题解 P3369 【【模板】普通平衡树（Treap/SBT）】

Great_Influence · 2018-05-31 16:58:40 · 题解

来一发leafytree题解。(今年论文新出的神秘数据结构)

当你写二叉平衡树的时候，因为每个节点的儿子数不同导致讨论冗杂，容易出错。并且常用的几个数据结构中，treap适用范围较小，splay常数巨大且不支持可持久化，替罪羊树等其余数据结构代码量大或复杂，细节多，不易实现。那么，有没有一种神奇的数据结构，能够解决这个问题呢?

~~你为什么不问问神奇海螺呢?~~

答案就是leafytree。

#### 1.插入和维护平衡 $leafytree$和其它的二叉搜索树一样，需要保证左边的节点权值大于右边的节点。因此，我们可以选择递归的方法来插入节点。对每个节点其下辖存储区间内的最大值(即右端点)。每次插入时，将左子树的最大点和插入节点的权值作比较。选择节点所属范围的一边即可。插入的时候加入一个叶子节点的同时也会加入一个辅助节点。然而极易发现，这种插入方法可以被轻松卡成一条链。这样明显是不行的。因此考虑使用一些方法来维护平衡。可以再次引入替罪羊树中的平衡因子思想，如果失衡到某一个子树的$size$比全树的$size$乘上平衡因子还要小，则认为其已经失衡，需要维护。维护失衡的方法可以选择拍扁重建，也可以选择$rotate$。因为拍扁重建和替罪羊树基本一样，所以在此不再介绍。考虑用$rotate$来维护平衡。定义一个节点的平衡度为$\displaystyle\frac{size[l]}{size[x]}$(假设此时左子树比右子树小)。考虑单旋和双旋对平衡度的影响。例如单旋:(如下图，设$size[Y]>size[a]$) ![此处应有图片](https://cdn.luogu.com.cn/upload/pic/20330.png) ![此处也应有图片](https://cdn.luogu.com.cn/upload/pic/20331.png) 设$X$旋转前的平衡度为$\rho_1$,$Y$旋转前的平衡度为$\rho_2$，旋转后分别为$\gamma_1$和$\gamma_2$。通过简单计算可以知道: $\gamma_1=\displaystyle\frac{\rho_1}{\rho_1+(1-\rho_1)\rho_2}

\gamma_2=\rho_1+(1-\rho_1)\rho_2

同理，对于双旋，有:(图见下方)

\gamma_1=\displaystyle\frac{\rho_1}{\rho_1+(1-\rho_1)\rho_2\rho_3}

\gamma_2=\displaystyle\rho_1+(1-\rho_1)\rho_2\rho_3

\gamma_3=\displaystyle\frac{\rho_2(1-\rho_3)}{1-\rho_2\rho_3}

此时考虑对于平衡因子\alpha的选取。可以证明，当\displaystyle\alpha<1-\frac{\sqrt2}{2}时，可以通过这两种操作来使新的节点平衡度处于[\alpha,1-\alpha]之内。当然此时选择\displaystyle\alpha=1-\frac{\sqrt2}{2}最合适。

至于维护的方法，就是当发现树失衡时，根据较小树的平衡度\rho进行讨论。如果\displaystyle\rho<\frac{1-2\alpha}{1-\alpha}时，进行一次单旋。否则进行一次双旋。

我的代码中有一个newnode函数和一个delet函数，是用来回收节点的，可以不写。

代码:

inline bool isr(int x){return x==son[fa[x]][1];}

inline void rotate(int x)//简单平衡树的旋转操作(一模一样)
{
    static int f,ff,k;f=fa[x];ff=fa[f];k=isr(x);
    son[fa[son[x][k^1]]=f][k]=son[x][k^1];
    son[fa[x]=ff][isr(f)]=x;
    son[fa[f]=x][k^1]=f;
    refresh(f);refresh(x);
    if(f==rt)rt=x;
}

const double alp=1-sqrt(2)/2,lim=(1-2*alp)/(1-alp);

inline void maintain(int x)//保持平衡
{
    static int dir;
    if(son[x][0])//非叶子节点才需要维护平衡
    {
        if(sz[son[x][0]]<sz[x]*alp)dir=1;//找到较小的一个子树
        else if(sz[son[x][1]]<sz[x]*alp)dir=0;
        else return;//没有失衡则跳出
        if(sz[son[son[x][dir]][dir^1]]>=sz[son[x][dir]]*lim)//分情况分类讨论
            rotate(son[son[x][dir]][dir^1]);
        rotate(son[x][dir]);
    }
}

void insert(int now,int x)
{
    if(!rt){rt=newnode(x);return;}//特判根节点
    if(sz[now]==1)//找到叶子结点
    {
        fa[son[now][0]=newnode(x)]=now;//开启新节点，当前叶子结点下放
        fa[son[now][1]=newnode(ma[now])]=now;
        if(x>ma[now])swap(son[now][0],son[now][1]);
    }
    else insert(son[now][x>ma[son[now][0]]],x);//向下递归
    refresh(now);//维护
    maintain(now);
}

2.删除

发现因为节点只会删去叶子结点，所以只需要将结点直接删去，其父亲叶子结点由另一棵子树代替，也被删除。

代码:

void del(int now,int x)
{
    int dir=x>ma[son[now][0]],t;
    if(sz[son[now][dir]]==1)//找到叶子结点
    {
        delet(son[now][dir]);//直接删掉
        fa[t=son[now][dir^1]]=fa[now];//用另一棵子树替代辅助节点并删除
        son[fa[now]][isr(now)]=t;
        delet(now);
        if(now==rt)rt=t;//特判根的情况
        now=t;
    }
    else del(son[now][dir],x);//向下递归
    refresh(now);//维护
    maintain(now);
}

3.求结点rank

这个和普通平衡树基本一样。但是因为每个节点的size实际上只是叶子结点数量，所以分类讨论的细节大大减少。

代码:

int find_by_order(int now,int x)
{
    if(sz[now]==1)return now;//找到叶子结点即返回
    if(sz[son[now][0]]>=x)return find_by_order(son[now][0],x);//递归查找
    else return find_by_order(son[now][1],x-sz[son[now][0]]);
}

4.找到第k大元素

和普通平衡树差不多。同样也少了很多细节。

代码:

int order_of_key(int now,int x)
{
    if(x<=mi[now])return 0;//数字不在范围内则返回0
    if(sz[now]==1)return 1;//找到叶子返回1
    if(ma[son[now][0]]>=x)return order_of_key(son[now][0],x);//递归求解
    else return sz[son[now][0]]+order_of_key(son[now][1],x);
}

5.查找前驱/后继

直接按照定义来查找就可以了。

代码:

int pre(int now,int x)
{
    if(sz[now]==1)return now;
    if(mi[son[now][1]]>=x)return pre(son[now][0],x);
    else return pre(son[now][1],x);
}

int suf(int now,int x)
{
    if(sz[now]==1)return now;
    if(ma[son[now][0]]>x)return suf(son[now][0],x);
    else return suf(son[now][1],x);
}

经过测试，本程序速度优秀。在自带大常数情况下，在我自己打的几种不同平衡树中，仅次于01trie(如果这也算的话)。

整体代码:

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#define Rep(i,a,b) for(register int i=(a),i##end=(b);i<=i##end;++i)
#define Repe(i,a,b) for(register int i=(a),i##end=(b);i>=i##end;--i)
#define For(i,a,b) for(i=(a),i<=(b);++i)
#define Forward(i,a,b) for(i=(a),i>=(b);--i)
#define Chkmin(a,b) a=a<b?a:b
#define Chkmax(a,b) a=a>b?a:b
#define pb push_back

inline void read(int &x)
{
    static const int BUFSIZE = 1048576;
    static char buf[BUFSIZE];
    static char *bufnow = buf;
    static char *bufmax = buf;
    if (bufnow == bufmax) {
        bufmax = buf + fread(buf, 1, BUFSIZE, stdin);
        bufnow = buf;
    }
    static int c,f;
    f=1;
    c = *bufnow++;
    for (;!isdigit(c)&&(c^'-');c = *bufnow++) {
            if (bufnow == bufmax) {
            bufmax = buf + fread(buf, 1, BUFSIZE, stdin);
            bufnow = buf;
        }
    }
    if(!isdigit(c)){f=-1;c=*bufnow++;}
    x = 0;
    for (;isdigit(c);c = *bufnow++) {
        x = (x << 1) + (x << 3) + c - 48;
        if (bufnow == bufmax) {
            bufmax = buf + fread(buf, 1, BUFSIZE, stdin);
            bufnow = buf;
        }
    }
    x*=f;
}

inline void write(int a,char ed='\n')
{
    static short s[13],tp;
    if(!a){putchar('0'),putchar(ed);return;}
    for(tp=0;a;a/=10)s[++tp]=a%10;
    for(;tp;putchar(s[tp--]^48));
    putchar(ed);
}
using namespace std;

const int MAXN=2e5+27;

static int n;

namespace leafy_tree
{
    const double alp=1.0-sqrt(2)/2,lim=(1-2*alp)/(1-alp);

    static int sz[MAXN],fa[MAXN],son[MAXN][2],ma[MAXN],mi[MAXN],rt;

    inline void refresh(int h)
    {
        if(son[h][0])
        {
            mi[h]=mi[son[h][0]];ma[h]=ma[son[h][1]];
            sz[h]=sz[son[h][0]]+sz[son[h][1]];
        }
    }

    inline bool isr(int x){return x==son[fa[x]][1];}

    inline void rotate(int x)
    {
        static int f,ff,k;f=fa[x];ff=fa[f];k=isr(x);
        son[fa[son[x][k^1]]=f][k]=son[x][k^1];
        son[fa[x]=ff][isr(f)]=x;
        son[fa[f]=x][k^1]=f;
        refresh(f);refresh(x);
        if(f==rt)rt=x;
    }

    inline void maintain(int x)
    {
        static int dir;
        if(son[x][0])
        {
            if(sz[son[x][0]]<sz[x]*alp)dir=1;
            else if(sz[son[x][1]]<sz[x]*alp)dir=0;
            else return;
            if(sz[son[son[x][dir]][dir^1]]>=sz[son[x][dir]]*lim)
                rotate(son[son[x][dir]][dir^1]);
            rotate(son[x][dir]);
        }
    }

    static int sta[MAXN],tp;

    inline int newnode(int x)
    {
        ma[sta[tp]]=mi[sta[tp]]=x;sz[sta[tp]]=1;
        return sta[tp--];
    }

    void insert(int now,int x)
    {
        if(!rt){rt=newnode(x);return;}
        if(sz[now]==1)
        {
            fa[son[now][0]=newnode(x)]=now;
            fa[son[now][1]=newnode(ma[now])]=now;
            if(x>ma[now])swap(son[now][0],son[now][1]);
        }
        else insert(son[now][x>ma[son[now][0]]],x);
        refresh(now);
        maintain(now);
    }

    inline void delet(int x)
    {son[x][0]=son[x][1]=fa[x]=sz[x]=0;sta[++tp]=x;}

    void del(int now,int x)
    {
        int dir=x>ma[son[now][0]],t;
        if(sz[son[now][dir]]==1)
        {
            delet(son[now][dir]);
            fa[t=son[now][dir^1]]=fa[now];
            son[fa[now]][isr(now)]=t;
            delet(now);
            if(now==rt)rt=t;
            now=t;
        }
        else del(son[now][dir],x);
        refresh(now);
        maintain(now);
    }

    int find_by_order(int now,int x)
    {
        if(sz[now]==1)return now;
        if(sz[son[now][0]]>=x)return find_by_order(son[now][0],x);
        else return find_by_order(son[now][1],x-sz[son[now][0]]);
    }

    int order_of_key(int now,int x)
    {
        if(x<=mi[now])return 0;
        if(sz[now]==1)return 1;
        if(ma[son[now][0]]>=x)return order_of_key(son[now][0],x);
        else return sz[son[now][0]]+order_of_key(son[now][1],x);
    }

    int pre(int now,int x)
    {
        if(sz[now]==1)return now;
        if(mi[son[now][1]]>=x)return pre(son[now][0],x);
        else return pre(son[now][1],x);
    }

    int suf(int now,int x)
    {
        if(sz[now]==1)return now;
        if(ma[son[now][0]]>x)return suf(son[now][0],x);
        else return suf(son[now][1],x);
    }
}

using namespace leafy_tree;

inline void work()
{
    read(n);
    Rep(i,1,(n<<1)+10)sta[i]=i;tp=(n<<1)+10;
    static int opt,x;
    insert(rt,-2147483647);
    insert(rt,2147483647);
    Rep(i,1,n)
    {
        read(opt);read(x);
        switch(opt)
        {
            case 1:insert(rt,x);break;
            case 2:del(rt,x);break;
            case 3:printf("%d\n",order_of_key(rt,x));break;
            case 4:printf("%d\n",ma[find_by_order(rt,x+1)]);break;
            case 5:printf("%d\n",ma[pre(rt,x)]);break;
            case 6:printf("%d\n",ma[suf(rt,x)]);break;
        }
    }
}

inline void file()
{
    #ifndef ONLINE_JUDGE
    freopen("water.in","r",stdin);
    freopen("water.out","w",stdout);
    #endif
}

int main()
{
    file();
    work();
    cerr<<1.0*clock()/CLOCKS_PER_SEC<<endl;
    return 0;
}

ex.leafy tree的其他扩展

它能够支持可持久化，且时间复杂度稳定$O(logn)$，常数比$FHQ$要更小。它能够合并与分裂，时间复杂度为$O(logn)$，且常数比$FHQ$小。 ~~总之就是比FHQ好用~~ 并且它的形式和线段树相似，区间操作更加简单。尽早学习，也可以作为一种常数优秀的简单平衡树来使用吧。