2019-09-02 22:00 算法工程师

关注

题解 | 算法竞赛进阶指南-普通平衡树

普通平衡树

http://www.nowcoder.com/questionTerminal/2ab2e260d4ab42899f1bb026ae96cf1f

WBLT 全称Weight Balanced Leafy Tree.是一种常数较小，代码较简单的平衡树实现方式。

在看本文之前，推荐您先学习treap等平衡树这篇文章对于有平衡树基础的人较为友好

定义和引入

WBLT是二叉搜索树的一种。不同的是，他同时是一个大根堆（也可以是小根堆），每个非叶节点都有两个儿子，且每个节点的权值与其右儿子的权值相同，且左儿子的权值小于右儿子的权值，左子树的所有节点的权值小于右子树任意节点的权值。

也就是说他大概长这样：

这种设计有一个明显的缺点就是如果要储存n个数据，普通的平衡树需要开n个节点，而WBLT需要开2n-1个

也就是说储存上图的数据的treap长这样：

那么相比之下它有什么好处呢？

旋转

WBLT= Weight Balanced Tree（加权平衡树） + Leafy，其中Leafy已经在_定义和引入_中体现了，平衡是指一个节点的左子树和右子树大小近似相同，这样在查询/修改的时候才能做到近似log，旋转便是维护平衡的方便手段

因为其结构特殊不需要像treap一样引入一个rand，只要旋转就可以维护其平衡。

先给出旋转的代码

inline void merge(int l,int r){
    size[++cnt]=size[l]+size[r];
    val[cnt]=val[r];
    ls[cnt]=l,rs[cnt]=r;
}

inline void rotate(int cur,bool flag){
    if(flag){
        merge(ls[cur],ls[rs[cur]]);
        ls[cur]=cnt;
        rs[cur]=rs[rs[cur]];
    }//左旋
    else{
        merge(rs[ls[cur]],rs[cur]);
        rs[cur]=cnt;
        ls[cur]=ls[ls[cur]];
    }//右旋
}

再给出图例（节点上的数字为编号，数字颜色为红色则为新节点）：

可以发现，旋转后的WBLT仍然保持原来的性质。而且明显偏重的左子树转到了右边，左右子树相对平衡了。

查询排名为x的数

我们记录每个节点的size，这个size不是子树的大小，而是子树储存的有效信息的大小。

因为有性质_储存n个数据要开2n-1个节点_，所以如果一个子树的大小为 $2x-1$ ，那它储存的数据量就有 $x$ 个。

接下来的操作就简单了，令find(cur,x)为寻找cur所在的子树下排名为x的数，那么当x比左子树的size小

$find(cur,x)=find(lson_{cur},x)$

当x比左子树的size大

$find(cur,x)=find(rson_{cur},x-size_{lson_{cur}})$

如果相等，那显然

$find(cur,x)=val_{cur}$

因为当前要找的是第x大，那我无需遍历下面，这点也与treap不同

int find(int cur,int x){
    if(size[cur]==x)
        return val[cur];
    if(x>size[ls[cur]])
        return find(rs[cur],x-size[ls[cur]]);
    return find(ls[cur],x);
}

查询x的排名

同理，设rnk(cur,x)为寻找cur子树下x的排名

当x小于cur的左儿子的权值

$rnk(cur,x)=rnk(lson_{cur},x)$

否则

$rnk(cur,x)=size_{lson_{cur}}+rnk(rson_{cur},x)$

int rnk(int cur,int x){
    if(size[cur]==1)
        return 1;
    if(x>val[ls[cur]])
        return rnk(rs[cur],x)+size[ls[cur]];
    return rnk(ls[cur],x);
}

插入

WBLT其他的操作都与treap类似，在每一步时：

根据要添加的权值和当前搜索到的节点选择左右子树进行递归（如果比左儿子的权值大就去右子树，否则去左子树）

递归到最后一步到一个叶子节点时，根据其权值大小建立新节点，确定是该节点的左儿子还是右儿子

建立它的兄弟节点。

向上pushup（类似于线段树，儿子会影响父亲，这点于与treap不同）。

void insert(int cur,int x){
    if(size[cur]==1){
        newnode(ls[cur],minn(x,val[cur]));
        newnode(rs[cur],maxx(x,val[cur]));
        pushup(cur);
        return ;
    }
    insert(x>val[ls[cur]]?rs[cur]:ls[cur],x);
    pushup(cur);
}

删除

在每一步时：

根据要删除权值和当前搜索到的节点选择左右子树进行递归（如果比左儿子的权值大就去右子树，否则去左子树）

递归到最后一步到一个叶子节点时，判断该节点是不是要删除的，如果不是则选择其兄弟节点，进行删除，将两个节点中保留的与其父亲节点进行替换

向上pushup。

void erase(int cur,int x){
    if(size[cur]==1){
        cur= ls[fa]==cur?rs[fa]:ls[fa];
        copynode(fa,cur);
        return ;
    }
    fa=cur;
    erase(x>val[ls[cur]]?rs[cur]:ls[cur],x);
    pushup(cur);
}

等等旋转呢？

我们在上文所有的操作中，似乎没有使用旋转，那旋转放在哪呢？

我们将其放在树的结构有改变的地方，也就是插入删除这些操作中，每当一个子树过大，就进行相应的旋转，在插入和删除操作中加入以下函数即可

const int ratio=5;

inline void maintain(int cur){
    if(size[ls[cur]]>size[rs[cur]]*ratio)
        rotate(cur,0);
    else if(size[rs[cur]]>size[ls[cur]]*ratio)
        rotate(cur,1);
}

那么普通平衡树的代码如下

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>

using namespace std;

const int maxn=400010;
const int ratio=5;

int n,cnt,fa,root;
int size[maxn],ls[maxn],rs[maxn],val[maxn];

inline void newnode(int &cur,int v){
    cur=++cnt;
    size[cur]=1;
    val[cur]=v;
}

inline void copynode(int x,int y){
    size[x]=size[y];
    ls[x]=ls[y],rs[x]=rs[y];
    val[x]=val[y];
}

inline void merge(int l,int r){
    size[++cnt]=size[l]+size[r];
    val[cnt]=val[r];
    ls[cnt]=l,rs[cnt]=r;
}

inline void rotate(int cur,bool flag){
    if(flag){
        merge(ls[cur],ls[rs[cur]]);
        ls[cur]=cnt;
        rs[cur]=rs[rs[cur]];
    }
    else{
        merge(rs[ls[cur]],rs[cur]);
        rs[cur]=cnt;
        ls[cur]=ls[ls[cur]];
    }
}

inline void maintain(int cur){
    if(size[ls[cur]]>size[rs[cur]]*ratio)
        rotate(cur,0);
    else if(size[rs[cur]]>size[ls[cur]]*ratio)
        rotate(cur,1);
}

inline void pushup(int cur){
    if(!size[ls[cur]])return ;
    size[cur]=size[ls[cur]]+size[rs[cur]];
    val[cur]=val[rs[cur]];
}

inline int minn(int a,int b){
    return a<b?a:b;
}
inline int maxx(int a,int b){
    return a>b?a:b;
}

inline void insert(int cur,int x){
    if(size[cur]==1){
        newnode(ls[cur],minn(x,val[cur]));
        newnode(rs[cur],maxx(x,val[cur]));
        pushup(cur);
        return ;
    }
    maintain(cur);
    insert(x>val[ls[cur]]?rs[cur]:ls[cur],x);
    pushup(cur);
}

inline void erase(int cur,int x){
    if(size[cur]==1){
        cur= ls[fa]==cur?rs[fa]:ls[fa];
        copynode(fa,cur);
        return ;
    }
    maintain(cur);
    fa=cur;
    erase(x>val[ls[cur]]?rs[cur]:ls[cur],x);
    pushup(cur);
}

inline int find(int cur,int x){
    if(size[cur]==x)
        return val[cur];
    maintain(cur);
    if(x>size[ls[cur]])
        return find(rs[cur],x-size[ls[cur]]);
    return find(ls[cur],x);
}

inline int rnk(int cur,int x){
    if(size[cur]==1)
        return 1;
    maintain(cur);
    if(x>val[ls[cur]])
        return rnk(rs[cur],x)+size[ls[cur]];
    return rnk(ls[cur],x);
}

int main(){
    scanf("%d",&n);
    newnode(root,(1<<30));
    while(n--){
        int s,x;
        scanf("%d%d",&s,&x);
        if(s==1)insert(root,x);
        if(s==2)erase(root,x);
        if(s==3)printf("%d\n",rnk(root,x));
        if(s==4)printf("%d\n",find(root,x));
        if(s==5)printf("%d\n",find(root,rnk(root,x)-1));
        if(s==6)printf("%d\n",find(root,rnk(root,x+1)));
    }
    return 0;
}

以下是评测记录

上面的是treap，下面的是WBLT（O2，scanf读入）

我们发现，WBLT只比treap慢一点点，所以WBLT和treap几乎是一样块的~

例题

P1503 鬼子进村

平衡树部分是个裸题，其他倒还得想想

先把0和n+1插入，作为边界

摧毁节点就插入该点

删除上一个就维护个栈，删除栈顶即可

询问操作就查找前驱和后继，一减就行了，记得特判是否已经被摧毁（记个vis数组即可）

代码

P2596 [ZJOI2006]书架

平衡树部分还是个裸题

定义优先级越小，那本书就放越上面

设 $a_i$ 为编号为 $i$ 的书本的优先级， $mapp_i$ 为优先级为i的节点编号。

Top S:将优先级变为最小再插入

Bottom S：将优先级变为最大再插入

Insert S T：找到对应两本书交换优先级

Ask S：查询优先级排名

Query S：查询第k小的优先级对应的编号

代码:

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<map>

using namespace std;

const int maxn=400010;
const int ratio=5;

inline int read(){
    register int num=0,flag=1;char ch;
    while((ch=getchar())<'0'||ch>'9') if(ch=='-') break;
    if(ch=='-') flag=-1;
    else num=ch-'0';
    while((ch=getchar())>='0'&&ch<='9') num=num*10+ch-'0';
    return num*flag; 
}
void out(int x){
    if(x>=10) out(x/10);
    putchar(x%10+'0');
}

int n,m,cnt,fa,root;
int size[maxn],ls[maxn],rs[maxn],val[maxn],a[maxn];
int mapp[maxn];

/*此处有省略，平衡树部分请参照上文*/

char opt[20];
int k,l,r,i;

int main() {
    n=read();
    m=read();
    newnode(root,(1<<30));
    l=233333,r=n+233333;
    for(i=1; i<=n; i++) {
        int qaq;
        qaq=read();
        insert(root,i+233333);
        a[qaq]=i+233333;
        mapp[i+233333]=qaq;
    }
    while(m--) {
        scanf("%s",opt);
        if(opt[0]=='Q') {
            k=read();
            out(mapp[find(root,k)]);
            putchar('\n');
        } else if(opt[0]=='A') {
            k=read();
            out(rnk(root,a[k])-1);
            putchar('\n');
        } else if(opt[0]=='T') {
            k=read();
            erase(root,a[k]);
            insert(root,--l);
            a[k]=l;
            mapp[l]=k;
        } else if(opt[0]=='B') {
            k=read();
            erase(root,a[k]);
            insert(root,++r);
            a[k]=r;
            mapp[r]=k;
        } else if(opt[0]=='I') {
            register int s=read(),t=read();
            if(t==1) {
                int rnk2=rnk(root,a[s]),rnk1=rnk2+1;
                int s2=find(root,rnk1);
                s2=mapp[s2];
                erase(root,a[s]);
                erase(root,a[s2]);
                swap(a[s],a[s2]);
                mapp[a[s]]=s;
                mapp[a[s2]]=s2;
                insert(root,a[s]);
                insert(root,a[s2]);
            } else if(t==-1) {
                int rnk2=rnk(root,a[s]),rnk1=rnk2-1;
                int s2=find(root,rnk1);
                s2=mapp[s2];
                erase(root,a[s]);
                erase(root,a[s2]);
                swap(a[s],a[s2]);
                mapp[a[s]]=s;
                mapp[a[s2]]=s2;
                insert(root,a[s]);
                insert(root,a[s2]);
            }
        }
    }
    return 0;
}

结果这个吊打了splay ，和fhq-treap差不了多少

而且似乎比同种思路的treap快了300ms左右