历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

cht讲算法——数据结构n锅端（3）——BST与Treap

作者：

cht , 2021-02-16 16:01:31 , 所有人可见 , 阅读 613

13

7

你看就算现在点赞+收藏没到15，我也周更了

数据结构n锅端（3）——BST与Treap

视频

BST

二叉搜索树是一种非常不错的数据结构。

基本定义：

在一个BST中，左儿子 < 根节点 < 右节点

所以说什么啊，一个BST的中序遍历是严格单调递增的。

所以说只要我们维护好BST性质，那么数据结构基本无敌。

基本的原因是因为会被卡。

这个以后再说。

先看一下基本的操作：左旋和右旋。

这两个操作分别表示将当前节点和左右儿子交换位置，同时满足BST性质。

这就是一个模拟，比较有难度。

第一次写可能有一点难，但是以后就习惯了。

void zig(int &u)
{
    int q = tr[u].l;
    tr[u].l = tr[q].r;
    tr[q].r = u;
    u = q;
    pushup(tr[u].r);
    pushup(u);
}
void zag(int &u)
{
    int q = tr[u].r;
    tr[u].r = tr[q].l;
    tr[q].l = u;
    u = q;
    pushup(tr[u].l);
    pushup(u);
}

注意到这里有一个pushup，表示用左儿子和右儿子更新当前的节点。

其实这个也还好。

void pushup(int u)
{
    tr[u].size = tr[tr[u].l].size + tr[tr[u].r].size + tr[u].cnt;//这个size和cnt的作用一会再说
}

然后就是新建节点了，$val$你们先别管。

$key$表示的是BST中点的权值。

int new_node(int k)
{
    tr[ ++ idx].k = k;
    tr[idx].val = rand();
    tr[idx].cnt = 1;
    tr[idx].size = 1;
    return idx;
}

下面的各种操作我就暂时不写代码了。

首先是插入操作。

这个可以先判断一下是否有。

因为此时是按照BST顺序找的，所以没有的话就直接newnode了。

然后是删除，也可以用和插入差不多的办法，利用BST是性质一点点找。

后面的几个操作一会再说。

Treap = BST + heap

首先我们发现，BST会被凉心出题人卡。

假如所有数有序，BST就退化成了一条链，然后就T非了。

期望高度证明

好看完了证明，我们发现，只要让BST随机，那就不会被卡。

所有平衡树的原理都是让BST尽量随机——yxc

你不信？

比如替罪羊树，它有一个平衡系数，只要不够平衡就直接重新做，算是最暴力的做法了吧。

今天我们讨论的版本是Treap，当然是旋转版的。~~(分裂合并的我也不会啊~~

我们来观察一下，不够随机的本质问题就是，这BST太按规则了，没有什么限制。

如果说我们能通过不断转哟让树足够随机再加上一个限制条件，这不就不会被卡了吗？？

那这个限制条件就是——堆

好吧有些大佬就会说了：

如果把一个点转到根节点不也可以维护平衡吗？

的确，那是splay，以后再说~~（突然感觉自己挖了个大坑~~

是不是突然明白了$val$的含义？

没错，$val$就是点在堆中的权值。

那么的话左旋和右旋的作用就是让平衡树“保持平衡”。

那么左旋和右旋的话还是一样的，不用变。

我们来看一下Treap支持哪些操作：

插入
删除
求前驱（小于x的最大数）
求后继（大于x的最小数）
求最大
求最小
求x的排名
求排名为x的数

注意插入和删除操作都是单点的，不支持区间的

所以我们来试着分析一下吧！！

屏幕截图 2021-02-16 153858.png

插入$6$，我们按照BST的性质，我们发现$6$大于$4$。

所以的话要往哪边走呢？没错就是右边。

同理，$6$ 大于 $5$，所以把$6$插到$5$的右边。

那么删除也是同理的。

屏幕截图 2021-02-16 153909.png

每次我们按照和插入同样的进行比较大小，然后我们再删除就行了。

排名什么的大家看代码的写法吧。

还有就是要记录$cnt$表示一个数出现了几次，$size$表示子树大小。

这些方便找排名或者前驱后继。

题目

题目描述

您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：

插入数值x。
删除数值x(若有多个相同的数，应只删除一个)。
查询数值x的排名(若有多个相同的数，应输出最小的排名)。
查询排名为x的数值。
求数值x的前驱(前驱定义为小于x的最大的数)。
求数值x的后继(后继定义为大于x的最小的数)。

输入格式

第一行为n，表示操作的个数。

接下来n行每行有两个数opt和x，opt表示操作的序号(1<=opt<=6)。

输出格式

对于操作3,4,5,6每行输出一个数，表示对应答案。

数据范围

$n \le 100000$,所有数均在$-10^7$到$10^7$内。

样例

输入样例：

输出样例：

板子题，提到了Treap能干的大部分操作。

我们来挨个实现一下。

左旋/右旋

void zig(int &u)//左右旋，没啥好说的，自己在纸上画一下就知道了
{
    int q = tr[u].l;
    tr[u].l = tr[q].r;
    tr[q].r = u;
    u = q;
    pushup(tr[u].r);
    pushup(u);//最后一定要记得上传，不然完了
}
void zag(int &u)
{
    int q = tr[u].r;
    tr[u].r = tr[q].l;
    tr[q].l = u;
    u = q;
    pushup(tr[u].l);
    pushup(u);
}

上传

和线段树的很像，主要计算$size$。

void pushup(int u)
{
    tr[u].size = tr[tr[u].l].size + tr[tr[u].r].size + tr[u].cnt;//上传节点信息，更新size
}

建树

记得建立两个哨兵，防止越界。

int new_node(int k)
{
    tr[ ++ idx].k = k;
    tr[idx].val = rand();//尽量随机，随手给个就行
    tr[idx].cnt = 1;
    tr[idx].size = 1;
    return idx;
}
void build()//建树操作，为了正确性增加两个哨兵，防止越界
{
    new_node(-INF), new_node(INF);
    root = 1, tr[1].r = 2;//初始化一下
    pushup(root);//上传信息
    if(tr[1].val< tr[2].val) zag(root);//不平衡了就旋转
}

插入

这里维护了$cnt$，所以插入删除的时候记得特判一下。

还有就是要维护堆性质，记得随时左右旋。

void insert(int &u, int k)
{
    if(u == 0) u = new_node(k);//如果走到空了，就新建
    else
    {
        if(tr[u].k == k)//如果找到了相同的节点，就cnt++
        {
            tr[u].cnt ++;
        }
        else
        {
            if(tr[u].k > k)//否则看看是在左边还是在右边
            {
                insert(tr[u].l, k);
                if(tr[tr[u].l].val > tr[u].val) zig(u);//不平衡立马调整
            }
            else
            {
                insert(tr[u].r, k);
                if(tr[tr[u].r].val > tr[u].val) zag(u); 
            }
        }
    }
    pushup(u);//最后上传一下，是不是和线段树有点像啊？
}

删除

这个没有难度，跟插入几乎差不多

void del(int &u, int k)//删除操作
{
    if(u == 0) return ;//如果没了说明节点不存在，就不管了。
    if(tr[u].k == k)//如果找到了这个点
    {
        if(tr[u].cnt > 1) tr[u].cnt --;//大于一好说，直接cnt --
        else//不大于一
        {
            if(tr[u].l || tr[u].r)//先看看是不是叶节点
            {
                if(!tr[u].r || tr[tr[u].l].val) 
                {
                    zig(u);
                    del(tr[u].r, k);//记得维护平衡哦
                }
                else
                {
                    zag(u);
                    del(tr[u].l, k);
                }
            }
            else u = 0;//是的话不用考虑平衡问题，直接删就是了
        }
    }
    else if(tr[u].k > k) del(tr[u].l, k);//如果没有找到就判断一下在左右两边的哪一边
    else del(tr[u].r, k);//找一下
    pushup(u);//上传更改
}

四个奇怪操作

分别是找前驱/后继，找排名/排名为x的数。

前驱/后继的做法是分类讨论+递归，能简短很多。

int get_pr(int u, int k)//前驱
{
    if(u == 0) return -INF;
    if(tr[u].k >= k) return get_pr(tr[u].l, k);//找左边
    return max(get_pr(tr[u].r, k), tr[u].k);//可能是右边可能是这个数，所以用个max
}
int get_ne(int u, int k)//后继
{
    if(u == 0) return INF;//后继的写法和前驱相反，大家可以注意一下
    if(tr[u].k <= k) return get_ne(tr[u].r, k);
    return min(get_ne(tr[u].l, k), tr[u].k);
}

另外两个也可以分类讨论，就是稍微复杂了一些，代码中有注释，大家注意一下。

int get_rank(int u, int k)
{
    if(u == 0) return 0;//是0随便返回就行
    if(tr[u].k == k) return tr[tr[u].l].size + 1;//相等了那排名应该就是左边的数量加上自己
    if(tr[u].k > k) return get_rank(tr[u].l, k);//大了找左边
    return tr[tr[u].l].size + tr[u].cnt + get_rank(tr[u].r, k);//找右边
} 
int get_key(int u, int rank)
{
    if(u == 0) return INF;
    if(tr[tr[u].l].size >= rank) return get_key(tr[u].l, rank);//找左边
    if(tr[tr[u].l].size + tr[u].cnt >= rank) return tr[u].k;//如果满足条件就直接return
    return get_key(tr[u].r, rank - tr[tr[u].l].size - tr[u].cnt);//不然就找右边
}

完整代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 100010, INF = 1e8;
int n;
struct Node
{
    int l, r;
    int k;
    int val;//堆中的编号
    int cnt, size;
}tr[N];
int root, idx;
void pushup(int u)
{
    tr[u].size = tr[tr[u].l].size + tr[tr[u].r].size + tr[u].cnt;//上传节点信息，更新size
}
int new_node(int k)
{
    tr[ ++ idx].k = k;
    tr[idx].val = rand();//尽量随机，随手给个就行
    tr[idx].cnt = 1;
    tr[idx].size = 1;
    return idx;
}
void zig(int &u)//左右旋，没啥好说的，自己在纸上画一下就知道了
{
    int q = tr[u].l;
    tr[u].l = tr[q].r;
    tr[q].r = u;
    u = q;
    pushup(tr[u].r);
    pushup(u);//最后一定要记得上传，不然完了
}
void zag(int &u)
{
    int q = tr[u].r;
    tr[u].r = tr[q].l;
    tr[q].l = u;
    u = q;
    pushup(tr[u].l);
    pushup(u);
}
void build()//建树操作，为了正确性增加两个哨兵，防止越界
{
    new_node(-INF), new_node(INF);
    root = 1, tr[1].r = 2;//初始化一下
    pushup(root);//上传信息
    if(tr[1].val< tr[2].val) zag(root);//不平衡了就旋转
}
void insert(int &u, int k)
{
    if(u == 0) u = new_node(k);//如果走到空了，就新建
    else
    {
        if(tr[u].k == k)//如果找到了相同的节点，就cnt++
        {
            tr[u].cnt ++;
        }
        else
        {
            if(tr[u].k > k)//否则看看是在左边还是在右边
            {
                insert(tr[u].l, k);
                if(tr[tr[u].l].val > tr[u].val) zig(u);//不平衡立马调整
            }
            else
            {
                insert(tr[u].r, k);
                if(tr[tr[u].r].val > tr[u].val) zag(u); 
            }
        }
    }
    pushup(u);//最后上传一下，是不是和线段树有点像啊？
}
void del(int &u, int k)//删除操作
{
    if(u == 0) return ;//如果没了说明节点不存在，就不管了。
    if(tr[u].k == k)//如果找到了这个点
    {
        if(tr[u].cnt > 1) tr[u].cnt --;//大于一好说，直接cnt --
        else//不大于一
        {
            if(tr[u].l || tr[u].r)//先看看是不是叶节点
            {
                if(!tr[u].r || tr[tr[u].l].val) 
                {
                    zig(u);
                    del(tr[u].r, k);//记得维护平衡哦
                }
                else
                {
                    zag(u);
                    del(tr[u].l, k);
                }
            }
            else u = 0;//是的话不用考虑平衡问题，直接删就是了
        }
    }
    else if(tr[u].k > k) del(tr[u].l, k);//如果没有找到就判断一下在左右两边的哪一边
    else del(tr[u].r, k);//找一下
    pushup(u);//上传更改
}
int get_rank(int u, int k)
{
    if(u == 0) return 0;//是0随便返回就行
    if(tr[u].k == k) return tr[tr[u].l].size + 1;//相等了那排名应该就是左边的数量加上自己
    if(tr[u].k > k) return get_rank(tr[u].l, k);//大了找左边
    return tr[tr[u].l].size + tr[u].cnt + get_rank(tr[u].r, k);//找右边
} 
int get_key(int u, int rank)
{
    if(u == 0) return INF;
    if(tr[tr[u].l].size >= rank) return get_key(tr[u].l, rank);//找左边
    if(tr[tr[u].l].size + tr[u].cnt >= rank) return tr[u].k;//如果满足条件就直接return
    return get_key(tr[u].r, rank - tr[tr[u].l].size - tr[u].cnt);//不然就找右边
}
int get_pr(int u, int k)//前驱
{
    if(u == 0) return -INF;
    if(tr[u].k >= k) return get_pr(tr[u].l, k);//找左边
    return max(get_pr(tr[u].r, k), tr[u].k);//可能是右边可能是这个数，所以用个max
}
int get_ne(int u, int k)//后继
{
    if(u == 0) return INF;//后继的写法和前驱相反，大家可以注意一下
    if(tr[u].k <= k) return get_ne(tr[u].r, k);
    return min(get_ne(tr[u].l, k), tr[u].k);
}
int main()
{
    build();//建树，要是忘了就凉了
    cin >> n;
    while(n --)
    {
        int op, x;
        cin >> op >> x;
        if(op == 1) insert(root, x);
        else if(op == 2) del(root, x);
        else if(op == 3) cout << get_rank(root, x) - 1 << endl;
        else if(op == 4) cout << get_key(root, x + 1) << endl;
        else if(op == 5) cout << get_pr(root, x) << endl;
        else cout << get_ne(root, x) << endl;//读入操作并进行处理
    }//结束了！！！下次再见！！
    return 0;
}

//顺便安利一发题解

作者：cht
链接：https://www.acwing.com/solution/content/34398/
来源：AcWing  
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。