平衡树基础

关于平衡树

平衡树是一棵二叉搜索树,但是它比二叉搜索树好的地方是可以避免一些情况下树退化成链而造成的O(n)的单词查找。而平衡树可以可以稳定在约O(logn)级别。但是这也并不是一定的,平衡树退化的可能性是有的,但是非常非常小,小到可以忽略不计。

平衡树是可以替代掉二叉搜索树的。由于二叉搜索树极限情况效率太低,所以很少有题目用它。
前置知识:二叉搜索树
重点知识:旋转、split操作和merge操作(亦可用于左偏树)
平衡树将其平衡的条件是rnd数组,使其同时具有堆和二叉树的性质。而堆的值随机生成,可以挽救大多数出题人卡时间的情况。(当然我前几天看到了一个手动生成随机数的题解)

Treap

Treap是一种平衡树的实现方法,在实际操作中并无太大作用。但是需要掌握它的思想。

Treap的核心思想是左旋和右旋。
左旋
右旋
(以上图片摘自这个博客

每一次添加或删除时从根节点加进,然后依次查找、判断大小并旋转,移到正确上。和BST的基础代码差不多。

代码

(没写过,不会写,懒得写)

由于Treap码量较大也没啥用,所以这篇博客的重点并不是Treap。

fhq-Treap

这个数据结构维护的是一个不用旋转的平衡树。

它不旋转,但是直接手撕平衡树再组装上去(好像更加暴力的样子)。

我们对于每一个插入a的操作,都先将小于等于a的搞到一边,把大于a的搞到另一边,分为两棵树。(这个操作有点难以理解,但是码量小)

然后merge的时候就把a和第一棵树拼一下,再和另一棵树拼一下。(这个操作并不是随便乱拼,而是根据其随机值拼)

删除操作是先将<=a-1的分到一边,然后将>a-1的分为<=a的和>a的,于是我们就得到了a(可以用cnt记录下每一个数出现的次数以将其存于一个节点中,但是这个在查询的时候会有一丝麻烦)。

然后我们将a这棵树的左节点和右节点放在一起,就把作为根节点的a孤立下来丢掉了。

kth操作没什么好多讲(当时查了三个小时的是谁啊?)

好的我们直接看代码。

代码

#include<bits/stdc++.h>
using namespace std;
const int Maxn=2000005;
int n,m;
int root;
int ch[Maxn][4],rnd[Maxn],val[Maxn],siz[Maxn];
int tot=0;
int newnode(int v){
    tot++;
    rnd[tot]=rand();
    val[tot]=v;
    siz[tot]=1;
    return tot;
}
void update(int now){
    siz[now]=siz[ch[now][0]]+siz[ch[now][5]]+1;
}
int merge(int x,int y){
    if(!x||!y)return x+y;
    if(rnd[x]<rnd[y]){ch[x][6]=merge(ch[x][7],y);update(x);return x;}
    else{ch[y][0]=merge(x,ch[y][0]);update(y);return y;}
}
void split(int now,int a,int &x,int &y){//注意这里的&,即在下一层中的更改会导致这一层的变量更改
    if(!now){
        x=y=0;
        return ;
    }
    if(val[now]<=a)x=now,split(ch[now][8],a,ch[now][9],y);
    else y=now,split(ch[now][0],a,x,ch[now][0]);
    update(now);
}
int kth(int now,int x){
    while(now){
        if(siz[ch[now][0]]+1<x)x-=siz[ch[now][0]]+1,now=ch[now][10];
        else if(siz[ch[now][0]]+1==x){return now;}
        else if(siz[ch[now][0]]+1>x)now=ch[now][0];
    }
}
int ans=0;
int main(){
    srand((unsigned)time(NULL));
    scanf("%d%d",&n,&m);
    int a;
    int x,y,z;
    for(int i=1;i<=n;i++){
        scanf("%d",&a);
        split(root,a,x,y);
        root=merge(merge(x,newnode(a)),y);
    }
    int op;
    int an=0;
    for(int i=1;i<=m;i++){
        scanf("%d%d",&op,&a);
        a^=an;
        if(op==1){
            split(root,a,x,y);
            root=merge(merge(x,newnode(a)),y);
        }else if(op==2){
            split(root,a,x,z);
            split(x,a-1,x,y);
            y=merge(ch[y][0],ch[y][11]);
            root=merge(merge(x,y),z);
        }else if(op==3){
            split(root,a-1,x,y);
            an=siz[x]+1;
            root=merge(x,y);
            ans^=an;
        }else if(op==4){
            an=val[kth(root,a)];
            ans^=an;
        }else if(op==5){
            split(root,a-1,x,y);
            an=val[kth(x,siz[x])];
            ans^=an;
            root=merge(x,y);
        }else if(op==6){
            split(root,a,x,y);
            an=val[kth(y,1)];
            ans^=an;
            root=merge(x,y);
        }
    }
    printf("%d",ans);
    return 0;
}

split操作可参考下图
split操作的示意图
(此图摘自洛谷日报)

本文链接:http://kaispace.com.cn/index.php/archives/655/

如果未注明出处,复制公开后需将注明本博客链接。
打赏作者