平衡树挺难的,于是乎水一篇题解。顺便记录一下!
题目描述
您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作:
- 插入数值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$内。
样例
输入样例:
8
1 10
1 20
1 30
3 20
4 2
2 10
5 25
6 -1
输出样例:
2
20
20
20
平衡树,Treap
众所周知Treap = BST + heap
堆不多说了。
说说这个BST,就是说一个根节点p,左儿子一定小于他,右儿子大于它。
也就是BST的中序遍历是严格单调递增的。
那么就可以进行一些操作了。
首先为了维护这个BST我们需要一个左旋zag和右旋zig,分别表示将根节点和左右儿子交换位置,使交换后还满足BST的性质。
这个相当于一个模拟了,代码放在后面。
然后就是插入。
这个可以从根节点开始,看看往左儿子走还是往右儿子走,一直走到空或者和自己相等的节点,然后进行插入。
删除的话也是一样,从根节点走,走到了这个节点就删除掉,如果走到的节点为空,那就不用管了,因为这个节点不存在。
还有就是删除的时候如果遇到了叶节点可以直接删除,不会影响BST的性质。
接着就是几个奇怪的操作。
先说最大最小,就是一直往左走或者一直往右走。
然后是查排名和排名对应的数,一样的,排名可以一点点走,然后分类讨论,这个可以看代码注释。
排名对应的数也是一样,但这个得判断一下个数,所以BST里要有cnt和size两个变量表示节点个数和当前这个节点有多少个。
最后是前驱和后继,具体定义参见题目描述。
方法也是一样,前驱就是左边最大的,后继就是右边最小的,可以用递归写,会简单很多。
但是有的时候BST会退化成一条链,时间复杂度就大大降低了,但是只要BST够随机,期望高度就是log n。
所以的话就把它和堆集合在了一起,变成了平衡树。
其他的注释我放到代码里了。
c++ 代码:
#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;
}
BST是传说中的万恶之源拜托大佬看下这个:
inline void zig1 (int &x)
{
int l = node[x].l;
node[x].l = node[l].r;
node[l].r = x;
x = l;
updSize (node[x].r);
updSize (x);
}
inline void zig2 (int &x)
{
Node &cur = node[x];
int l = cur.l;
cur.l = node[l].r;
node[l].r = x;
x = l;
updSize (cur.r);
updSize (x);
}
zig1 能用, zig2 不能。
其他地方换成引用也是这个毛病QAQ
佬
if(!tr[u].r || tr[tr[u].l].val)
{
zig(u);
del(tr[u].r, k);//记得维护平衡哦
}
是不是有点问题
不应该是!tr[p].r || tr[tr[p].l].val > tr[tr[p].r].val吗
堆确定上下顺序,BST确定左右顺序,假设BST确定,那么上下顺序决定平衡,而堆中每个数都是随机的,可以说一个数相对另一个数,在它上面还是下面的概率是50%,当树很大时,加入一个新的数,按照概率这个数,大概率是在中间(上下顺序),为什么(额类比抛硬币),所以加入的数大概在最后一两层,配合旋转操作,基本是平衡的。
%%%%%%%%%%%
但是有的时候BST会退化成一条链,时间复杂度就大大降低了
不是应该时间复杂度大大升高了吗?
不,高手都叫提高!
chtyyds!hpzc
您tql
nononoOrz
stcccco
大佬,能帮我解释下两个哨兵的原因吗,我就这个点没听懂
val有什么用呢,为什么要随机,不会乱了吗
这颗二叉树是靠val来保证它整得像二叉树,而不会退化. 就像AVL树需要维护平衡因子一样,当大根堆的性质出现问题的时候,通过旋转就能让它一直保持二叉树的形态. 这样增删改查都是logn级别
说的真好
随机的,才是真实的,才是均匀的。人为构造的,都是极端的,都是反人类的,都是需要骂出题人的。
大佬,能帮我解释下两个哨兵的原因吗,我就这个点没听懂
兄弟,为什么del函数里面 if(!tr[u].r || tr[tr[u].l].val) 这样是对的,为什么不是if (!tr[u].r || tr[tr[u].l].val > tr[tr[u].r].val)啊
else if(op == 4) cout << get_key(root, x + 1) << endl;
这句话是什么意思?查询排名第 $\verb!x!$ 的数为什么要 $\verb!+1? !$
@cht
有两个哨兵啊
左旋和右旋的push交换顺序为什么不影响结果呢
上传左右节点的信息,应该是对称的
请问大佬,如何理解 treap 中的随机权值会避免普通BST的复杂度退化情况的发生呢?
是否是说,生成的随机数的话,是很难完全严格单调的?
不是的
那里有一个证明,随机BST的期望高度是O(logn)的,随机权值只是随便给的,主要的是堆会把二叉搜索树的不稳定性完全锁死,就是key和val确定,Treap的构造也就确定了。
嗯,然后证明这个随机权值很难使得treap的深度达到 O(N) 吗?
不是,就是说堆的val值一旦确定了,key也确定的话,这颗BST是唯一的,除非对BST进行旋转改变val的值
对的,由插入序列
key
和随机生成的堆值序列val
可以唯一确定 treap 的形状,这个我是明白的,不过如何证明期望高度为 O(log N),感觉还是有点迷糊,可能也不是很重要吧!我记得快排的时间复杂度证明也是很复杂的。嗯
左旋zag和右旋zig是大家的一个约定吗?我看这两个单词的意思好像都是一样的。
应该是的
嗯呢
分享的底料,博客这两天就更