平衡树学习笔记

Study

FHQ Treap

前置芝士

BST的性质:
根节点左子树的值均小于等于根节点，右子树的值均大于根节点 

例题

我们需要支持以下操作

split

inline void split(int now, int &x, int &y, int k){ //裂开 
    if(!now) return (void)(x = y = 0); //如果没有根即没有树可裂，x，y均为0 
    if(val[now] <= k){
        x = now; //如果根的值小于等于k则k要大于now左子树所有的值，所以把左子树裂开，让右子树接着裂 
        split(ch[now][1], ch[x][1], y, k);
    }else{
        y = now; //相反 
        split(ch[now][0], x, ch[y][0], k);
    }
    up(now);
    //裂开以后所有比k小的值均在x树上，比k大的值均在y树上 
} 

merge

inline void merge(int &now, int x, int y){
    if(!siz[x] or !siz[y]) return (void)(now = siz[x] ? x : y); //x 和 y 有一个空树的话直接返回不空树 
    if(key[x] < key[y]){ //当x的键值小于y的键值 ，让y和x的右子树并 
        now = x;
        merge(ch[now][1], ch[x][1], y); 
        up(now);
    }else{
        now = y;//相反 
        merge(ch[now][0], x, ch[y][0]);
        up(now);
    }
} 

delete

如何删除一个数num，很巧妙的方法

1.我们把root树以num为关键字裂开，此时x树上的值均小于等于num

2.我们再去裂x树，此时以num-1为关键字，则裂开的两个树中有一个树上的值均等于 num（我们设这颗树为z）

3.直接合并z的左右子树，此时已经把z的根节点移除

4.合并

inline void del(int num){ 
    split(root, x, y, num);
    split(x, x, z, num-1);
    merge(z, ch[z][0], ch[z][1]);
    merge(x, x, z);
    merge(root, x, y);
}

insert

很简单

inline void ins(int num){
    split(root, x, y, num);
    merge(x, x, new_node(num));
    merge(root, x, y);
}

kth

寻找第k排名的数

（暂时还不透彻，会补上注释的....汗）

inline int kth(int now, int k){ 
    while(1){
        if(k <= siz[ch[now][0]]){
            now = ch[now][0];
        }else{
            if(k == siz[ch[now][0]] + 1) return now;
            else{
                k -= siz[ch[now][0]] + 1;
                now = ch[now][1];
            }
        }
    }
}

rnk

num的排名就是所有小于num的数的数量+1，此时已经显然

inline int rnk(int num){
    split(root, x, y, num-1);
    int res = siz[x] + 1;
    merge(root, x, y);
    return res;
}

pre

前驱怎么找？

前驱是不是所有小于num的值里最大的值！

我们以num-1为关键字去把root树裂开，此时x树上的值是所有小于num的数，

我们再找x树里面排名为size[x]的数，是不是就是所有小于num的数里面最大的数？即前驱。

inline int pre(int num){ //找前驱 
    split(root, x, y, num-1);
    int res = val[kth(x,siz[x])];
    merge(root, x, y);
    return res;
}

nxt

后继怎么找...

后继是不是所有大于num的值里最小的值.....

我们以num为关键字去把root树裂开，此时y树上的值是所有大于num的数，

我们再找y树里面排名为1的数，是不是就是所有大于num的数里面最小的数？即后继。

inline int nxt(int num){
    split(root, x, y, num);
    int res = val[kth(y,1)];
    merge(root, x, y);
    return res;
}

总代码看不看无所谓的吧，反正就是并在一起了....

code

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
struct Treap{
    int ch[maxn][2], val[maxn], key[maxn], siz[maxn];
    int sum, root, x, y, z, n; //sum记录节点编号 
    inline void up(int now){ //维护一下大小 
        siz[now] = siz[ch[now][0]] + siz[ch[now][1]] + 1; //它的大小就等于左右儿子大小的和+自己这个点 
    }
    inline int new_node(int num){ //新建一个点 
        siz[++sum] = 1; //新建一个树(点)，但大小为1 
        val[sum] = num; //值为num 
        key[sum] = rand(); //随机 
        return sum; //返回节点编号 
    }
    inline void split(int now, int &x, int &y, int k){ 
        if(!now) return (void)(x = y = 0);
        if(val[now] <= k){
            x = now;
            split(ch[now][1], ch[x][1], y, k);
        }else{
            y = now;
            split(ch[now][0], x, ch[y][0], k);
        }
        up(now);
    } 
    inline void merge(int &now, int x, int y){ 
        if(!siz[x] or !siz[y]) return (void)(now = siz[x] ? x : y);
        if(key[x] < key[y]){
            now = x;
            merge(ch[now][1], ch[x][1], y); 
            up(now);
        }else{
            now = y;
            merge(ch[now][0], x, ch[y][0]);
            up(now);
        }
    } 
    inline void del(int num){ 
        split(root, x, y, num);
        split(x, x, z, num-1);
        merge(z, ch[z][0], ch[z][1]);
        merge(x, x, z);
        merge(root, x, y);
    }
    inline void ins(int num){
        split(root, x, y, num);
        merge(x, x, new_node(num));
        merge(root, x, y);
    }
    inline int kth(int now, int k){
        while(1){
            if(k <= siz[ch[now][0]]){
                now = ch[now][0];
            }else{
                if(k == siz[ch[now][0]] + 1) return now;
                else{
                    k -= siz[ch[now][0]] + 1;
                    now = ch[now][1];
                }
            }
        }
    }
    inline int rnk(int num){
        split(root, x, y, num-1);
        int res = siz[x] + 1;
        merge(root, x, y);
        return res;
    }
    inline int pre(int num){
        split(root, x, y, num-1);
        int res = val[kth(x,siz[x])];
        merge(root, x, y);
        return res;
    }
    inline int nxt(int num){
        split(root, x, y, num);
        int res = val[kth(y,1)];
        merge(root, x, y);
        return res;
    }
    void main(){
        root = 0, x = y = z = 0;
        scanf("%d", &n);
        for(int i = 1, q, w; i <= n; i ++){
            scanf("%d%d", &q, &w);
            if(q == 1) ins(w);
            if(q == 2) del(w);
            if(q == 3) printf("%d\n", rnk(w));
            if(q == 4) printf("%d\n", val[kth(root,w)]);
            if(q == 5) printf("%d\n", pre(w));
            if(q == 6) printf("%d\n", nxt(w));
        }
    }
}FHQ;
signed main(){
    FHQ.main();
    return 0;
} 

Splay

wanqua