替罪羊树学习笔记
山田リョウ
·
·
算法·理论
这里效果更佳
替罪羊树是一种简单粗暴的平衡树，它在一颗子树不平衡的时候会把整棵子树拍扁重构。
简单说一下替罪羊树是怎么插入删除的：
- 插入：类似普通 bst，但是在回溯的过程中多了一步维护子树。
- 删除：先找到这个节点，然后把该节点的副本数减一（如果副本数为 1 的话，减一就变成了 0，此时就相当于这个节点已经删除了），再在回溯的过程中维护平衡。
然后我们要说说每个节点要维护哪些信息了：
- v，权值
- lc和rc，左儿子和右儿子的编号
- c，副本数
- s1，指的是这个节点的子树中的节点个数
- s2，指的是这个节点的子树中还存在的节点个数（即副本数不为 0 的节点个数）
- s3，指的是这个节点的子树中的元素个数（每个节点算副本数遍）
struct node{
int v,lc,rc,c,s1,s2,s3;
node():v(0),lc(0),rc(0),c(0),s1(0),s2(0),s3(0){}
}tree[maxn];
inline void pushup(const int&x){
tree[x].s1=tree[tree[x].lc].s1+tree[tree[x].rc].s1+1,
tree[x].s2=tree[tree[x].lc].s2+tree[tree[x].rc].s2+(tree[x].c!=0),
tree[x].s3=tree[tree[x].lc].s3+tree[tree[x].rc].s3+tree[x].c;
}
现在我们再说说如何维护平衡：
替罪羊树是根据子树大小来判断是否平衡的，首先，我们需要先设定一个平衡值 \alpha（0.5<\alpha<1），我喜欢将其设定为 \frac{3}{4}。当一个节点的两个儿子的 s1 的最大值比这个节点的 s1
如果发现不平衡，就按照中序遍历将其拍扁然后重构，注意，在拍扁的过程中如果发现一个节点已经被删除了就别再放到拍扁的数列里了。
```cpp
void dfs(const int&x){
if(!tree[x].s2)return ;
dfs(tree[x].lc);
if(tree[x].c)ldr[ldr_cnt++]=x;
dfs(tree[x].rc);
}
void build(int&x,int l,int r){
if(l==r){x=0;return;}
int mid=l+r>>1;x=ldr[mid];
build(tree[x].lc,l,mid);
build(tree[x].rc,mid+1,r);
pushup(x);
}
inline void maintain(int&x){
pushup(x);
if(tree[x].s1*3<=max(tree[tree[x].lc].s1,tree[tree[x].rc].s1)*4||tree[x].s2*4<=tree[x].s1*3){
ldr_cnt=0;
dfs(x);
build(x,0,ldr_cnt);
}
}
```
`ins` 和 `del` 上面都说了怎么做了，而查询操作和普通 bst 类似，就不说了，直接放代码：
```cpp
#include<stdio.h>
#include<ctype.h>
#define getc()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
inline void read(int&x){
char c=getc(),f=0;x=0;
for(;!isdigit(c);c=getc())f^=!(c^45);
for(;isdigit(c);c=getc())x=(x<<1)+(x<<3)+(c^48);
if(f)x=-x;
}
const int maxn=1e5+1;
struct node{
int v,lc,rc,c,s1,s2,s3;
node():v(0),lc(0),rc(0),c(0),s1(0),s2(0),s3(0){}
}tree[maxn];
int nodecnt,ldr[maxn],ldr_cnt;
inline int max(int a,int b){return a>b?a:b;}
inline void pushup(const int&x){
tree[x].s1=tree[tree[x].lc].s1+tree[tree[x].rc].s1+1,
tree[x].s2=tree[tree[x].lc].s2+tree[tree[x].rc].s2+(tree[x].c!=0),
tree[x].s3=tree[tree[x].lc].s3+tree[tree[x].rc].s3+tree[x].c;
}
void dfs(const int&x){
if(!tree[x].s2)return ;
dfs(tree[x].lc);
if(tree[x].c)ldr[ldr_cnt++]=x;
dfs(tree[x].rc);
}
void build(int&x,int l,int r){
if(l==r){x=0;return;}
int mid=l+r>>1;x=ldr[mid];
build(tree[x].lc,l,mid);
build(tree[x].rc,mid+1,r);
pushup(x);
}
inline void maintain(int&x){
pushup(x);
if(tree[x].s1*3<=max(tree[tree[x].lc].s1,tree[tree[x].rc].s1)*4||tree[x].s2*4<=tree[x].s1*3){
ldr_cnt=0;
dfs(x);
build(x,0,ldr_cnt);
}
}
void ins(int&x,const int&k){
if(!tree[x].s2)x=++nodecnt,tree[x].v=k,tree[x].c=1;
else if(k<tree[x].v)ins(tree[x].lc,k);
else if(k>tree[x].v)ins(tree[x].rc,k);
else ++tree[x].c;
maintain(x);
}
void del(int&x,const int&k){
if(!tree[x].s2) return;
if(k<tree[x].v)del(tree[x].lc,k);
else if(k>tree[x].v)del(tree[x].rc,k);
else --tree[x].c;
maintain(x);
}
int q_rnk(const int&x,const int&v){
if(!tree[x].s2)return 1;
if(v>tree[x].v) return tree[tree[x].lc].s3+tree[x].c+q_rnk(tree[x].rc,v);
return q_rnk(tree[x].lc,v);
}
int q_val(const int&x,const int&r){
if(r<=tree[tree[x].lc].s3)return q_val(tree[x].lc,r);
if(r>tree[tree[x].lc].s3+tree[x].c)return q_val(tree[x].rc,r-tree[tree[x].lc].s3-tree[x].c);
return tree[x].v;
}
int main(){
int rt=0,m,op,x;
read(m);
for(;m--;){
read(op),read(x);
switch(op){
case 1:ins(rt,x);break;
case 2:del(rt,x);break;
case 3:printf("%d\n",q_rnk(rt,x));break;
case 4:printf("%d\n",q_val(rt,x));break;
case 5:printf("%d\n",q_val(rt,q_rnk(rt,x)-1));break;
default:printf("%d\n",q_val(rt,q_rnk(rt,x+1)));
}
}
return 0;
}
```
其实替罪羊树应该还可以分裂合并，做法类似 rbt、AVL、BB[α]。
还有，很显然，替罪羊树的高度是 $O(\log n)$，所以查询的复杂度明显是 $O(\log n)$，但是插入删除时由于维护平衡需要拍扁重构整棵子树，所以复杂度是**均摊** 的 $\log n$。