抱歉,您的浏览器无法访问本站
本页面需要浏览器支持(启用)JavaScript
了解详情 >

treap = tree + heap,就比 BST 多了几行代码。

luogu 阅读链接

前言

无旋 treap
默认读者会 BST 的基本操作、堆的定义。
如果没有特殊声明,本文的 treap 都指旋转 treap。
本文使用的是小根堆。

思想

treap 既是一棵二叉查找树(tree),也是一个二叉堆(heap)。
但是如果这两个数据结构用同一个权值维护,那么这两种数据结构是矛盾的。
所以 treap 用了一个很巧妙的方式:给每个节点附加一个随机的优先级,让权值满足二叉查找树的结构,让优先级满足二叉堆的结构。
这个就是一棵 treap(黑色是权值,蓝色是随机的优先级):
tu
由于优先级只能随机赋予,堆不一定是一颗完全二叉树,所以 treap 是弱平衡(近似平衡)的。

旋转

在不改变中序遍历的情况下,旋转可以改变树的结构。
在 treap 中,我们用旋转来满足二叉堆,控制树高。
图中从左到右是右旋,从右到左是左旋。
tu
我们来模拟一下右旋的过程(左旋同理)。
tu
在实现中,我会把左右旋放在一起写。

1
2
3
4
5
6
void rotate(int&now, int dir){  
int t = d[now].ch[dir];
d[now].ch[dir] = d[t].ch[!dir];
d[t].ch[!dir] = now;
pushup(now), pushup(t), now = t; //now 是 t 的儿子了,先更新 now 再更新 t
}

这里的 rotate(x, 0) 表示将 lsxls_{x} 提到 xx 的高度,即右旋。
这里的 rotate(x, 1) 表示将 rsxrs_{x} 提到 xx 的高度,即左旋。

基础操作

节点变化

我们要在定义的时候添加一个优先级,然后在新建时给他赋随机值。

1
2
3
4
5
6
7
8
9
10
//需要头文件 <random>,<chrono>
std::mt19937 rd(std::chrono::steady_clock::now().time_since_epoch().count());
struct node{
int ch[2], size, val, rank;
}d[N];
int newnode(int x){
int w = ++tot;
d[w].val = x, ls(w) = rs(w) = 0, d[w].size = 1, d[w].rank = rd();
return w;
}

插入

只有在插入的那个子树的优先级可能变化。
如果优先级比当前节点小,那么我们把它旋转上来。
记得更新节点。

1
2
3
4
5
6
7
void insert(int&now, int val){
if(!now)return void(now = newnode(val));
int dir = d[now].val < val;
insert(d[now].ch[dir], val);
if(d[d[now].ch[dir]].rank < d[now].rank)rotate(now, dir);
if(now)pushup(now);
}

删除

这里我们需要改变一下目标节点有两个儿子的时候的方法。
我们比较两个儿子的优先级,把优先级小的旋转上来。
那么目标节点就到当前节点的另一侧,继续删除即可。
返回时要更新节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
void del(int&now, int val){
if(!now)return;
if(d[now].val == val){
if(ls(now) && rs(now)){
int z = d[rs(now)].rank < d[ls(now)].rank;//哪边的优先级小
rotate(now, z), del(d[now].ch[!z], val);//删除另一侧
}
else now = ls(now) ? ls(now) : rs(now);
}
else if(d[now].val < val)del(rs(now), val);
else del(ls(now), val);
if(now)pushup(now);//牢记
}

代码

P3369

可持久化

不知道什么是可持久化的戳
只需要在所有要修改节点的地方新建节点,有注释的是新加句子。
完整代码
修改片段:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void copynode(int &i){if(i)d[++tot] = d[i], i = tot;}//************
void rotate(int&now, int dir){
int t = d[now].ch[dir];
copynode(t);//************** now节点已经新建过了
d[now].ch[dir] = d[t].ch[!dir];
d[t].ch[!dir] = now;
pushup(now), pushup(t), now = t;
}
void insert(int&now, int val){
copynode(now);//****************
if(!now)return void(now = newnode(val));
int dir = d[now].val < val;
insert(d[now].ch[dir], val);
if(d[d[now].ch[dir]].rank < d[now].rank)rotate(now, dir);
if(now)pushup(now);
}
void del(int&now, int val){
copynode(now);//****************
if(!now)return;
if(d[now].val == val){
if(ls(now) && rs(now)){
int z = d[rs(now)].rank > d[ls(now)].rank;
rotate(now, z), del(d[now].ch[!z], val);
}
else now = ls(now) ? ls(now) : rs(now);
}
else if(d[now].val < val)del(rs(now), val);
else del(ls(now), val);
if(now)pushup(now);
}