树堆-TREAP
DHWJHY
2024-04-17 21:15:51
## 上集回顾-REVIEW
>>[《二叉搜索树（BST）》](https://www.luogu.com.cn/article/vqr2u9g2):
>>### 特异性进化-EVOLUTION FOR SPECIFICTY
>>
>>显然，满足 $\texttt{BST}$ 性质且中序遍历相同的二叉查找树不唯一，如此，有可能树的深度达到 $O(\frac{1}{2}n)$ ，从而被卡成 $O(n^2)$ 的时间复杂度，所以，我们想要把中序遍历相>同的二叉树确定下来，确定成深度维持在 $O(\log n)$ 的级别。
>>
>>于是，下一代数据结构登场——**堆树-TREAP**。
## 一、$\texttt{BST}$ 形态转换：旋转-THE RETATION OF $\texttt{BST}$
改变形态并维持 $\texttt{BST}$ 性质的方法为“**旋转**”。
分为**左旋**与**右旋**：
以右旋为例，在初始情况下，$x$ 是 $y$ 的左子节点，$A$ 和 $B$ 分别是 $x$ 的左右子树，$C$ 是 $y$ 的右子树。
“**右旋**”操作在保持 $\texttt{BST}$ 性质的基础上，把 $x$ 变为 $y$ 的父节点，因为 $x$ 的关键码小于 $y$ 的关键码，所以 $y$ 应该作为 $x$ 的右子节点。
当 $x$ 变成 $y$ 的父节点后，$y$ 的左子树就空出来了，于是 $x$ 原来的右子树 $B$ 就恰好作为 $y$ 的左子树。
其代码如下（定义按[《二叉搜索树（BST）》](https://www.luogu.com.cn/article/vqr2u9g2)中的例题代码）：
```cpp
void zig(int &p){//把 p 的左子节点与 p 合法换位
int q=a[p].l;
a[p].l=a[q].r;// 子节点的右子树成为 p 的左子树
a[q].r=p;//p 成为子节点的右子树
p=q;//p 是引用
}
```
对应的，左旋为：
```cpp
void zag(int &p){//把 p 的右子节点与 p 合法换位
int q=a[p].r;
a[p].r=a[q].l;// 子节点的左子树成为 p 的右子树
a[q].l=p;//p 成为子节点的左子树
p=q;//p 是引用
}
```
- ### 简记：左旋拎右左挂右，右旋拎左右挂左——AgOH
而这样的旋转操作可以**使 $\texttt{BST}$ 趋于平衡（左右子节点分布均匀）而不至于深度过大**，问题在于，如何旋转？
然而，**随机化**便是答案。
## 二、树堆-TREAP
发现，再随机数据下，普通的 $\texttt{BST}$ 是趋近于平衡的，$\texttt{Treap}$ 的思想就是利用“随机”来创造平衡条件。
我们的想法是**把“随机”作用在堆性质上**，这也是为什么要叫树堆。具体地讲，每个节点新添一个变量作为**随机域**或**重要性指数**，同时要求该数据结构**满足 $\texttt{BST}$ 性质与堆性质**。此时，其二叉搜索树的**形式唯一且深度较小**。
为什么深度较小？假设随机生成值与 $\texttt{BST}$ 中的权值对应，因为在随机下以随机生成值插入 $\texttt{heap}$ 后其结构期望为平衡的，在给原 $\texttt{BST}$ 旋转一下，能够找到对应结构，因而平衡。
## 三、例题实操-PRACTICE FOR AN EXAMPLE
然而，用例题来实操一下：[P3369 【模板】普通平衡树](https://www.luogu.com.cn/problem/P3369)。
我们可以发现，有一些与 $\texttt{BST}$ 类似的地方，所以就不再解释了，看[《二叉搜索树（BST）》](https://www.luogu.com.cn/article/vqr2u9g2)回顾。
然后，回顾堆的性质：[《堆-HEAP》](https://www.luogu.com.cn/article/r56rwn2r)。这里使用大根堆。
- ### initialization of the treap
三大基操（基本操作）：
```cpp
void pushup(int p){
tr[p].siz=tr[tr[p].l].siz+tr[tr[p].r].siz+tr[p].cnt;
}
void zig(int &p){//右旋
int q=tr[p].l;
tr[p].l=tr[q].r;
tr[q].r=p;
p=q;
pushup(tr[p].r),pushup(p);
}
void zag(int &p){//左旋
int q=tr[p].r;
tr[p].r=tr[q].l;
tr[q].l=p;
p=q;
pushup(tr[p].l),pushup(p);
}
```
结构体初始化，TREAP初始化：
```cpp
const int N = 1e5+10,inf = 1e8;
struct treap{
int l,r;
int key,val;//val是随机赋值域
int cnt,siz;
}tr[N];
int root,idx;
int add(int key){
tr[++idx].key=key;
tr[idx].val=rand();//随机域赋值
tr[idx].siz=tr[idx].cnt=1;
return idx;
}
void build(){
add(-inf),add(inf);
root=1,tr[1].r=2;
tr[1].cnt=tr[1].siz=tr[2].cnt=tr[2].siz=0;//哨兵无实意
pushup(root);
if(tr[1].val < tr[2].val) zag(root);
//万一随机有问题，然而 是否需要这么做 是有争议的，因为哨兵无实意
}
```
- ### insert
```cpp
void insert(int &p,int key){
if(!p) p=add(key);
else if(key==tr[p].key) tr[p].cnt++;
else if(key<tr[p].key){
insert(tr[p].l,key);
if(tr[tr[p].l].val>tr[p].val) zig(p);
}else{
insert(tr[p].r,key);
if(tr[tr[p].r].val>tr[p].val) zag(p);
}
pushup(p);
}
```
可以看到，我们总是在插入过程中通过旋转使结构合理的同时在叶子节点插入数据，这一点可以尽可能使树的深度较小，因此叫平衡树。
- ### delete（remove）
```cpp
void remove(int &p,int key){
if(!p) return ;
else if(key==tr[p].key){
if(tr[p].cnt>1) tr[p].cnt--;
else if(tr[p].r || tr[p].l){
if(!tr[p].r || tr[tr[p].l].val>tr[tr[p].r].val){
zig(p);
remove(tr[p].r,key);
}else{
zag(p);
remove(tr[p].l,key);
}
}else p=0;
}else if(tr[p].key>key) remove(tr[p].l,key);
else remove(tr[p].r,key);
pushup(p);
}
```
在删除之前，我们总是将要删除节点向子节点移动。
- ### get（rank by key/key by rank）
```cpp
int get_rank_by_key(int p,int key){
if(!p) return 1;
if(tr[p].key==key) return tr[tr[p].l].siz+1;
if(tr[p].key>key) return get_rank_by_key(tr[p].l,key);
return tr[tr[p].l].siz+tr[p].cnt+get_rank_by_key(tr[p].r,key);
}
int get_key_by_rank(int p,int rank){
if(!p) return inf;
if(tr[tr[p].l].siz>=rank)
return get_key_by_rank(tr[p].l,rank);
if(tr[tr[p].l].siz+tr[p].cnt>=rank) return tr[p].key;
return get_key_by_rank(tr[p].r,rank-tr[tr[p].l].siz-tr[p].cnt);
}
```
查询排名的过程就像走分叉路，然而通过 $\texttt{TREAP}$ 的性质我们知道，分叉路口的另一条路有时是有意义的（当查找数在右子树时，左子树中任意数都小于查找数；然而向左子树查询时，右子树中任意数都不小于查找数），所以，在查找过程中，加加减减的事是常有的。
- ### get lower-bound or upper-bound
```cpp
int get_pre(int p,int key){
if(!p) return -inf;
if(tr[p].key>=key) return get_pre(tr[p].l,key);
return max(tr[p].key,get_pre(tr[p].r,key));
}
int get_suf(int p,int key){
if(!p) return inf;
if(tr[p].key<=key) return get_suf(tr[p].r,key);
return min(tr[p].key,get_suf(tr[p].l,key));
}
```
其实，还有一种非递归的写法，但倘若递归用不了，那么 $\texttt{TREAP}$ 的大部分操作都用不了了。
```cpp
int get_pre(int p,int key){
int ans=1;
//tr[ans].key=-inf，初始化答案
while(p){
if(tr[p].key==key){
//若有查找数，则其pre一定是其左子树的最右子节点
if(tr[p].l){
p=tr[p].l;
while(tr[p].r) p=tr[p].r;
ans=p;
}
break;//直接找到
}
if(tr[p].key<key && tr[p].key>tr[ans].key) ans=p;
//尽可能更新答案
if(tr[p].key>key) p=tr[p].l;
else p=tr[p].r;
//p=(tr[p].key>key)?tr[p].l:tr[p].r;
}
return tr[ans].key;
}
int get_suf(int p,int key){
int ans=2;
//tr[ans].key=inf，初始化
while(p){
if(tr[p].key==key){
if(tr[p].r){
p=tr[p].r;
while(tr[p].l) p=tr[p].l;
ans=p;
}
break;
}
if(tr[p].key>key && tr[p].key<tr[ans].key) ans=p;
p=(tr[p].key<key)?tr[p].r:tr[p].l;
}
return tr[ans].key;
}
```
---
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10,inf = 1e8;
struct treap{
int l,r;
int key,val;
int cnt,siz;
}tr[N];
int root,idx;
int n;
void pushup(int p){
tr[p].siz=tr[tr[p].l].siz+tr[tr[p].r].siz+tr[p].cnt;
}
void zig(int &p){//右旋
int q=tr[p].l;
tr[p].l=tr[q].r;
tr[q].r=p;
p=q;
pushup(tr[p].r),pushup(p);
}
void zag(int &p){//左旋
int q=tr[p].r;
tr[p].r=tr[q].l;
tr[q].l=p;
p=q;
pushup(tr[p].l),pushup(p);
}
int add(int key){
tr[++idx].key=key;
tr[idx].val=rand();
tr[idx].siz=tr[idx].cnt=1;
return idx;
}
void build(){
add(-inf),add(inf);
root=1,tr[1].r=2;
tr[1].cnt=tr[1].siz=tr[2].cnt=tr[2].siz=0;
pushup(root);
if(tr[1].val < tr[2].val) zag(root);
}
void insert(int &p,int key){
if(!p) p=add(key);
else if(key==tr[p].key) tr[p].cnt++;
else if(key<tr[p].key){
insert(tr[p].l,key);
if(tr[tr[p].l].val>tr[p].val) zig(p);
}else{
insert(tr[p].r,key);
if(tr[tr[p].r].val>tr[p].val) zag(p);
}
pushup(p);
}
void remove(int &p,int key){
if(!p) return ;
else if(key==tr[p].key){
if(tr[p].cnt>1) tr[p].cnt--;
else if(tr[p].r || tr[p].l){
if(!tr[p].r || tr[tr[p].l].val>tr[tr[p].r].val){
zig(p);
remove(tr[p].r,key);
}else{
zag(p);
remove(tr[p].l,key);
}
}else p=0;
}else if(tr[p].key>key) remove(tr[p].l,key);
else remove(tr[p].r,key);
pushup(p);
}
int get_rank_by_key(int p,int key){
if(!p) return 1;
if(tr[p].key==key) return tr[tr[p].l].siz+1;
if(tr[p].key>key) return get_rank_by_key(tr[p].l,key);
return tr[tr[p].l].siz+tr[p].cnt+get_rank_by_key(tr[p].r,key);
}
int get_key_by_rank(int p,int rank){
if(!p) return inf;
if(tr[tr[p].l].siz>=rank)
return get_key_by_rank(tr[p].l,rank);
if(tr[tr[p].l].siz+tr[p].cnt>=rank) return tr[p].key;
return get_key_by_rank(tr[p].r,rank-tr[tr[p].l].siz-tr[p].cnt);
}
int get_pre(int &p,int key){
if(!p) return -inf;
if(tr[p].key>=key) return get_pre(tr[p].l,key);
return max(tr[p].key,get_pre(tr[p].r,key));
}
int get_suf(int &p,int key){
if(!p) return inf;
if(tr[p].key<=key) return get_suf(tr[p].r,key);
return min(tr[p].key,get_suf(tr[p].l,key));
}
int main(){
srand((unsigned)time(0));
build();
scanf("%d",&n);
while(n--){
int opt,x;
scanf("%d%d",&opt,&x);
if(opt==1) insert(root,x);
else if(opt==2) remove(root,x);
else if(opt==3) printf("%d\n",get_rank_by_key(root,x));
else if(opt==4) printf("%d\n",get_key_by_rank(root,x));
else if(opt==5) printf("%d\n",get_pre(root,x));
else printf("%d\n",get_suf(root,x));
}
return 0;
}
```