【平衡树】【替罪羊树】替罪羊树总结
替罪羊树是重量平衡树的一种，对于简单的平衡树应用，特别是维护的信息无法快速合并时，替罪羊树是个出色的选择。它的代码比较好理解，思想简单而暴力：对于一个节点，当左右子树的节点数量不平均时，我们就把它重构一遍。下面，我们重点阐述一下重构操作。
【基本操作】
1.拍扁重构操作：
当我们发现深度最浅的一个节点的子树不平衡时，我们从这个节点开始，对其子树进行中序遍历，同时用一个vector储存节点。代码中未提及的部分暂时忽略。
void collect(int t,vector<int>&v)
{
if(!t)return;
collect(ch[t][0],v);//遍历左子树
if(real[t])v.push_back(t);//保存当前节点
else del_place(t);
collect(ch[t][1],v);//遍历右子树
}
之后，我们从vector中找到最中间的节点，让它成为新的子树的根，然后递归构造它的左子树和右子树。由于是中序遍历，所以我们可以保证其二叉查找树的性质不被破坏。这样，我们得到的新的结构的树就是一个严格的完全二叉树，深度保证了严格的log。
int divide(int l,int r,vector<int> v)
//l,r是左闭右开的区间
{
if(l>=r)return 0;//当前区间为空
int mid=(l+r)>>1;
int t=v[mid];
ch[t][0]=divide(l,mid,v);
//递归构造左子树
ch[t][1]=divide(mid+1,r,v);
//递归构造右子树
fa[ch[t][0]]=fa[ch[t][1]]=t;
//确立父子关系
pushup(t);//维护子树信息
return t;//返回当前构造的子树的根
}
void rebuild(int &t)
{
static vector<int>v;
v.clear();
int f=fa[t];
collect(t,v);//中序遍历子树
t=divide(0,v.size(),v);//重构子树
fa[t]=f;
}
从代码中我们看得出的确很暴力，满满的O(n)。总结起来就是一句话：拍扁，拎起来。
2.删除操作
由于替罪羊树不是基于旋转的平衡树，它的删除操作不能通过移动节点达到目的。这里，我们用一个real数组表示当前节点是否被删除。为了更好地保证替罪羊树的时间复杂度，除了子树的size维护子树未删除的节点的个数，我们还需要用一个all数组表示当前子树所有节点个数（包括没有删除的和已经删除的节点）。如果大量删除的节点未得到清理的话，我们的时间复杂度难以得到保证，因此我们引入一个平衡因子作为阈值，当siz和all的比值大于这个阈值时，我们就重构整棵树，回收已经删除的节点，即上文collect函数的del_place函数。
void erase(int t,int k)
{
siz[t]--;
if(real[t]&&k==siz[ch[t][0]]+real[t]){real[t]=0;return;}
if(k<=siz[ch[t][0]])erase(ch[t][0],k);
else erase(ch[t][1],k-siz[ch[t][0]]-real[t]);
}
void erase(int vl)
{
erase(root,rank(vl));
if(siz[root]<alpha*all[root])rebuild(root);
//判断all和siz的比例，是否需要重构
}
3.回收空间
对于已经删除的节点，我们保存了它的儿子，父亲，siz，all等无用信息，十分浪费空间，因此我们用一个数组保存已经删除的节点，每当我们新建节点时，就优先使用已经删除的节点编号，如果没有，再执行++tot。
int st[N],top,tot;
int get_place(){return top?st[top--]:++tot;}
void del_place(int t){st[++top]=t;}
4.关于平衡树一般操作的注意
替罪羊树的一个很大的特点就是树中有一些已经删除的节点，因此我们在查找前驱后继或元素排名时一定要注意判断当前节点是否被删除。
5.插入操作
这个操作和一般的平衡树的插入操作差不多，只不过我们需要用一个变量res来保存深度最小的不合法的点，如果存在这样的点，我们就要对子树进行重构。
int insert(int &t,int vl)
{
if(!t)
{
t=newnode(vl);//新建节点
return 0;
}
siz[t]++;all[t]++;
int res;
int d= vl>val[t];//判断添加在左子树还是右子树
res=insert(ch[t][d],vl);//
pushup(t);
if(check(t))res=t;
return res;
//返回子树内深度最小的不平衡的点，没有则为0
}
void insert(int vl)
{
int t=insert(root,vl);
if(!t)return;
if(t==root)rebuild(root);
else{
int d=get(t);
rebuild(ch[fa[t]][d]);
}
}
6.平衡因子的选择
平衡因子是用于判断子树是否平衡以及all和siz的比例是否过大的一个常数。我们一般定为0.75。当然，具体情况具体分析，我们可以注意到平衡因子在略大的情况下，重构操作会变少，因此插入的时间会有所降低，但是树高也会因此变大，查找时间会增大。平衡因子在偏小的时候，重构操作会增多，因此插入时间复杂度增大，但是树高因此变小，查找操作的时间也变小。一般情况下取 0.6 到 0.7 左右的平衡因子就能满足大部分需求。对于一些各类操作数量极不均衡的题目，可以适当调整平衡因子的大小。
bool check(int t){return max(all[ch[t][0]],all[ch[t][1]])>=alpha*all[t];}
//返回1表示该子树不平衡
【小结】
替罪羊树虽然不基于旋转机制，但是其思路非常清晰，代码量非常的小，在速度上也不慢，无论是时间复杂度，实现复杂度和思维复杂度都不输给传统平衡树。但是替罪羊树由于其平衡机制的限制，并不能支持一些复杂的操作，比如常用Splay 来处理的提取区间的操作。同时由于它是一个用势能来分析的均摊结构，也无法简单的进行可持久化。对于简单的平衡树应用，特别是维护的信息无法快速合并时，替罪羊树是个出色的选择。
例题：【普通平衡树】
完整代码：
#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cmath>
#define re register
#define LL long long
using namespace std;
int n,m,a,b,c;
inline int red()
{
int data=0;int w=1; char ch=0;
ch=getchar();
while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar();
if(ch=='-') w=-1,ch=getchar();
while(ch>='0' && ch<='9') data=(data<<3)+(data<<1)+ch-'0',ch=getchar();
return data*w;
}
struct node{
static const int N=2e5+5;
static const double alpha=0.75;
int st[N],top,tot;
int get_place(){return top?st[top--]:++tot;}
void del_place(int t){st[++top]=t;}
void clean_st(){top=tot=0;}
int root;
int ch[N][2],fa[N];
int val[N],siz[N],all[N];
bool real[N];
void pushup(int p){
all[p]=all[ch[p][0]]+all[ch[p][1]]+1;
siz[p]=siz[ch[p][0]]+siz[ch[p][1]]+real[p];
}
bool check(int t){return max(all[ch[t][0]],all[ch[t][1]])>=alpha*all[t];}
int newnode(int w=0,int f=0){
int t=get_place();
ch[t][1]=ch[t][0]=0;
val[t]=w;
siz[t]=all[t]=1;
real[t]=1;
fa[t]=f;
return t;
}
void collect(int t,vector<int>&v)
{
if(!t)return;
collect(ch[t][0],v);
if(real[t])v.push_back(t);
else del_place(t);
collect(ch[t][1],v);
}
int divide(int l,int r,vector<int> v)
{
if(l>=r)return 0;
int mid=(l+r)>>1;
int t=v[mid];
ch[t][0]=divide(l,mid,v);
ch[t][1]=divide(mid+1,r,v);
fa[ch[t][0]]=fa[ch[t][1]]=t;
pushup(t);
return t;
}
void rebuild(int &t)
{
static vector<int>v;
v.clear();
int f=fa[t];
collect(t,v);
t=divide(0,v.size(),v);
fa[t]=f;
}
int rank(int vl)
{
int t=root,ans=1;
while(t)
{
if(vl<=val[t])t=ch[t][0];
else
{
ans+=siz[ch[t][0]]+real[t];
t=ch[t][1];
}
}
return ans;
}
int get_kth(int k)
{
int t=root;
while(t)
{
if(siz[ch[t][0]]+1==k&&real[t])return val[t];
if(siz[ch[t][0]]>=k)t=ch[t][0];
else{
k-=siz[ch[t][0]]+real[t];
t=ch[t][1];
}
}
}
int get(int u){return u==ch[fa[u]][1];}
int insert(int &t,int vl)
{
if(!t)
{
t=newnode(vl);
return 0;
}
siz[t]++;all[t]++;
int res;
int d= vl>val[t];
res=insert(ch[t][d],vl);
pushup(t);
if(check(t))res=t;
return res;
}
void insert(int vl)
{
int t=insert(root,vl);
if(!t)return;
if(t==root)rebuild(root);
else{
int d=get(t);
rebuild(ch[fa[t]][d]);
}
}
void erase(int t,int k)
{
siz[t]--;
if(real[t]&&k==siz[ch[t][0]]+real[t]){real[t]=0;return;}
if(k<=siz[ch[t][0]])erase(ch[t][0],k);
else erase(ch[t][1],k-siz[ch[t][0]]-real[t]);
}
void erase(int vl)
{
erase(root,rank(vl));
if(siz[root]<alpha*all[root])rebuild(root);
}
int pre(int vl){
return get_kth(rank(vl)-1);
}
int nxt(int vl){
return get_kth(rank(vl+1));
}
}sgt;
int main()
{
scanf("%d",&n);
while(n--)
{
int opt,t;
opt=red();t=red();
switch(opt)
{
case 1:sgt.insert(t);break;
case 2:sgt.erase(t);break;
case 3:printf("%d\n",sgt.rank(t));break;
case 4:printf("%d\n",sgt.get_kth(t));break;
case 5:printf("%d\n",sgt.pre(t));break;
case 6:printf("%d\n",sgt.nxt(t));break;
}
}
}