学习心得 - 数据结构 - 平衡树
ExFish
·
·
算法·理论
先来一波 Treap。
这个硬骨头我们看代码。
节点定义
struct node{ // An AVL node
int son[2];
int val;
int dat;
int sz;
int cnt;
}a[NODE];
$val$ 节点值。
$dat$ 节点优先级（随机）。
$sz$ 节点大小。
$cnt$ 相同节点覆盖（记录次数）。
### 增加节点
```cpp
int add(int val){ // Add An New Node.
++tot;
a[tot].val=val;
a[tot].dat=rnd();
a[tot].sz=1;
a[tot].cnt=1;
return tot;
}
```
很好理解吧。
看上面。
### 更新节点值
```cpp
void push(int p){ // Push Up To Father.
a[p].sz=
a[a[p].son[0]].sz+
a[a[p].son[1]].sz+
a[p].cnt;
}
```
更新子节点数量，注意加上自己。
### 建 AVL 树
```cpp
void build(){ // Build The TREAP :) It looks easy.
rt=add(-INF);
a[rt].son[1]=add(INF);
push(rt);
}
```
右倾，符合 BST。
### 旋转
这个图看看。
然后我们看代码。
```cpp
void rotate(int &p,int dir){ // Rotate!
int tmp=a[p].son[dir^1];
a[p].son[dir^1]=a[tmp].son[dir];
a[tmp].son[dir]=p;
p=tmp;
push(a[p].son[dir]);
push(p);
}
```
首先我们存一个儿子节点用于**旋转后更新数据**（$tmp$）。
接着，我们记录答案，修改 $p$，再更新自己的儿子即可。
### 插入
```cpp
void insert(int &p,int val){ // Insert!
if(!p){
p=add(val);
return;
}
if(val==a[p].val)a[p].cnt++; // Same.
else{ // Make BST!
int dir=!(val<a[p].val); // Rotate.
insert(a[p].son[dir],val);
if(a[p].dat<a[a[p].son[dir]].dat)rotate(p,dir^1);
}
push(p);
}
```
要是这个点不存在，就新建一个点。
否则，我们看是否有一个完全一样的点，那么我们将这个点的 $cnt$ 增加。
否则，递归。
我们旋转，看值是否符合，然后往子节点转。
要是优先级有问题，那么，转！
最后更新一下节点值。
### 最难的删除 qwq
```cpp
void remove(int &p,int val){
if(!p)return; // Null
if(val==a[p].val){
if(a[p].cnt>1){ // Delete
a[p].cnt--;
push(p);
return;
}
if(a[p].son[0]||a[p].son[1]){ // Only Son
if(!a[p].son[1]||a[a[p].son[0]].dat>a[a[p].son[1]].dat){
rotate(p,1);
remove(a[p].son[1],val);
}else{
rotate(p,0);
remove(a[p].son[0],val);
}
push(p);
}else p=0; // BoOm
return;
}
if(val<a[p].val)remove(a[p].son[0],val);
else remove(a[p].son[1],val);
push(p);
}
```
要是没点，结束。
要是值对了，删。
要是有重叠，删掉一个。
要是有儿子，优先删右儿子，再删左儿子。
删完儿子了，删自己。
要是值不对，那么去看子节点。
注意最后维护下值。
### 常用查询 查排名
```cpp
int getrnk(int p,int val){ // Get Rank.
if(!p)return 1;
if(val==a[p].val)return a[a[p].son[0]].sz+1;
else if(val<a[p].val)return getrnk(a[p].son[0],val);
return a[a[p].son[0]].sz+a[p].cnt+getrnk(a[p].son[1],val);
}
```
没什么技术含量，要是没点就返回标杆。
要是值对了，那么~~园艺杆菌炸炸炸！~~ 就返回答案。
要是值大了，看左儿子的。
要是值小了，那么看右儿子。
### 常用查询 查数值
```cpp
int getval(int p,int rnk){ // Get Val.
if(!p)return INF;
if(rnk<=a[a[p].son[0]].sz)return getval(a[p].son[0],rnk);
else if(rnk<=a[a[p].son[0]].sz+a[p].cnt)return a[p].val;
return getval(a[p].son[1],rnk-a[a[p].son[0]].sz-a[p].cnt);
}
```
~~妹纸~~没值，就是正无穷。
接着我们在左区间和右区间找即可。
### 找前驱 / 后驱
由于这两份代码只有一个符号不同，就以前驱为例子。
```cpp
int getprv(int val){ // Prev
int p=rt,pre;
while(p){
if(a[p].val<val){
pre=a[p].val;
p=a[p].son[1];
}else p=a[p].son[0];
}
return pre;
}
```
一直找一直找一直找，就是答案了喵。