平衡树：treap学习笔记（1）

平衡树是基于二叉查找树的一个数据结构。他的左右子树高度差不超过1。

二叉查找树插入时最坏情况下退化成一条链，查找复杂度O（n）。我们可以用平衡树来维护使得左右子树平衡，复杂度在O（logn）。

怎么平衡呢？我们用旋转来实现。在treap中有左旋和右旋两个操作。

左旋：将自己的左儿子变成父亲节点的右儿子，父亲节点变成自己的左儿子。

右旋是对称的。（代码中的p是这里说的父亲节点。

treap=tree+heap。他的优先级（随机数）以堆的形式排布，值域是二叉查找树的形式。

其实我觉得平衡树最难的部分是查找qaq。。。可能我还是太菜了。

#include<bits/stdc++.h>
using namespace std;

const int MAXN=+;

int my_rand(){
    static int seed=;
    return seed=int(seed*L%);
}


struct treap{
    int size[MAXN],lson[MAXN],rson[MAXN],prio[MAXN],w[MAXN];
    int cnt1,rt;
    void mem(){
        cnt1=,rt=;
        memset(w, , sizeof(w));
        memset(prio, , sizeof(prio));
        memset(size, , sizeof(size));
        memset(lson, , sizeof(lson));
        memset(rson, , sizeof(rson));
    }
    inline void pushup(int o){size[o]=size[lson[o]]+size[rson[o]]+;}
    inline void zuo(int &p){
        int tem=rson[p];
        rson[p]=lson[tem];
        lson[tem]=p;
        size[tem]=size[p];
        pushup(p);
        p=tem;
    }
    inline void you(int &p){
        int tem=lson[p];
        lson[p]=rson[tem];
        rson[tem]=p;
        size[tem]=size[p];
        pushup(p);
        p=tem;
    }
    inline void insert(int &p,int x){
        if(!p){
            p=++cnt;w[p]=x;size[p]=;prio[p]=my_rand();return;
        }
        size[p]++;
        insert((x>=w[p])?rson[p]:lson[p],x);
        if(lson[p]&&prio[lson[p]]<prio[p])you(p);
        if(rson[p]&&prio[rson[p]]<prio[p])zuo(p);
    }
    inline void del(int &p,int x){
        size[p]--;
        if(x==w[p]){
            if(!lson[p]&&!rson[p]){p=;return;}
            if(!lson[p]||!rson[p]){p=lson[p]+rson[p];return;}
            if(prio[lson[p]]<prio[rson[p]]){
                you(p);
                del(rson[p],x);
                return;     
            }
            else {
                zuo(p);
                del(lson[p],x);
                return;
            }           
        }
        del((x>=w[p])?rson[p]:lson[p],x);
    }
    inline int rank(int &p,int x){
        if(!p)return ;
        int ans=;
        if(w[p]<x)ans+=size[lson[p]]++rank(rson[p],x);
        else ans=rank(lson[p],x);
        return ans;
    }
    inline int rankshu(int &p,int x){
        if(x==size[lson[p]]+)return w[p];
        if(size[lson[p]]+<x) return rankshu(rson[p],x-size[lson[p]]-);
        else return rankshu(lson[p],x);
    }
    inline int rankpre(int &p,int x){
        if(!p)return ;
        if(w[p]>=x)return rankpre(lson[p],x);
        int tem=rankpre(rson[p],x);
        if(!tem)return w[p];
        else return tem;
    }
    inline int rankhou(int &p,int x){
        if(!p)return ;
        if(w[p]<=x)return rankhou(rson[p],x);
        int tem=rankhou(lson[p],x);
        if(!tem)return w[p];
        else return tem;
    }
}treap;

int n;
int main(){
//  freopen("1.in","r",stdin);
//  freopen("1.out","w",stdout);
    scanf("%d",&n);
    treap.mem();
    for(int i=;i<=n;i++){
        int opt, x;
        scanf("%d%d", &opt, &x);
        if(opt==)treap.insert(treap.rt,x);
        if(opt==)treap.del(treap.rt,x);
        if(opt==)printf("%d\n",treap.rank(treap.rt,x)+);
        if(opt==)printf("%d\n",treap.rankshu(treap.rt,x));
        if(opt==)printf("%d\n",treap.rankpre(treap.rt,x));
        if(opt==)printf("%d\n",treap.rankhou(treap.rt,x));
    }
    return ;
}