题解 P3369 【【模板】普通平衡树】
Nero_Claudius · · 题解
刚刚恶补了替罪羊树，由于一个指针出锅调了贼久，必须得写一篇题解巩固一下理解。
参考了ikka大佬的博客，我的替罪羊树就是在那里学会的。
替罪羊树是一种优越的平衡树，它不像Splay和Treap有着绚丽的旋转操作，而是朴实地暴力重构。
具体来说，为了保持树结构的平衡，替罪羊树在每一次插入和删除的时候都会判断树是否平衡，根据结果选择是否要重构子树。
明白了替罪羊树的思想之后实现其实不难（毕竟思路朴实）。
平衡判断
替罪羊树最核心的部分，也就是它判断树是否平衡的过程，是通过平衡因子来实现的。
这个名字听起来很霸气很高深，但其实就是一个0.5到1之间的浮点数罢了。
const double alpha = 0.75;当一颗树的左子树（或右子树）存在的节点数大于这棵树存在的节点数*平衡因子的时候，这颗树就是不平衡的。
这个过程我们会在后面用到。
节点结构体
struct Node{
int val,size,cover;
bool exist;
Node* ch[2];
void pushup(){this->size=ch[0]->size+ch[1]->size+(int)exist,this->cover=ch[0]->cover+ch[1]->cover+1;}
int isbad(){return (ch[0]->cover>this->cover*alpha+5)||(ch[1]->cover>this->cover*alpha+5);}
};val是节点的值，size是节点子树的大小，cover是节点存在的的节点个数。
exist是节点是否存在。
ch是左儿子与右儿子。
pushup操作很好理解，就是size和cover都更新一下。
isbad操作判断当前子树是否是不平衡的，原理就是之前讲的那个过程。（之所以加上5是怕不稳）
你可能会注意到，本文多次强调了“存在”这个概念，没错，替罪羊树不会真正删去节点，而是将它们变为“不存在”。
新节点
你可能会认为新建节点就是new node，然鹅这样太慢了。
为了提速，我们必须手动模拟内存池（其实我听到这个词是懵逼的）。
模拟内存池的流程就是，把所有不要的节点丢进内存回收池，然后需要的时候再提取出来。
这样删除掉的节点就不会浪费，而能得到有效利用。
Node mempool[N];
Node *tail,*null,*root;
Node *bc[N];
int bc_top;
Node* newNode(int val){
Node* p=bc_top?bc[--bc_top]:tail++;
p->ch[0]=p->ch[1]=null;
p->size=p->cover=p->exist=1;
p->val=val;
return p;
}mempool就是我们模拟的内存池。tail指向内存池内的元素。
root不用管它。
null是我们模拟的空节点其实没什么用。
bc是内存回收值，bc_top是回收池顶。
创建一个新节点的流程。。。其实我觉得不说你们也看得懂，那就不说了。
重构子树
这是最核心的部分，其根本思路是讲树拍成一个有序数列，然后再重新建树。
排成有序数列做一个中序遍历就可以了，只有存在的节点才加入数列。
建树也很简单，就每次数组折半，分治建即可。
void Travel(Node* p,vector<Node*>& x){
if(p==null)return;
Travel(p->ch[0],x);
if(p->exist)x.push_back(p);
else bc[bc_top++]=p;
Travel(p->ch[1],x);
}
Node* Divide(vector<Node*>& x,int l,int r){
if(l>=r)return null;
int mid=(l+r)>>1;
Node* p=x[mid];
p->ch[0]=Divide(x,l,mid);
p->ch[1]=Divide(x,mid+1,r);
p->pushup();
return p;
}
void Rebuild(Node*& p){
vector<Node*> x;
x.clear();
Travel(p,x);
p=Divide(x,0,x.size());
}数组你用啥都行，由于懒这里用vector。
实现没有什么好讲的。
插入节点
我个人认为，插入节点是替罪羊树最毒瘤的地方（指针不友好）。
插入节点在插入的同时，会返回指向指向不平衡的节点的指针的指针。
上面那句话就是我所谓的毒瘤（其实也不是很毒瘤），第一次可能会被绕地晕头转向。
之所以要返回指向指针的指针，是因为我们所有操作都需要指针。
Node** Insert(Node*& p,int val){
if(p==null){
p=newNode(val);
return &null;
}
p->size++,p->cover++;
Node** res=Insert(p->ch[val>=p->val],val);
if(p->isbad())res=&p;
return res;
}如果当前节点是空节点，那就新建一个节点，然后返回空节点（新的节点不会导致树不平衡）。
否则根据插入节点的值递归左右儿子。
然后假如当前节点子树不平衡，返回当前节点。
删除操作
删除操作很水，没什么技术含量。
void Erase(Node*& p,int k){
p->size--;
int offset=p->ch[0]->size+p->exist;
if(p->exist&&offset==k){
p->exist=false;
}else{
if(k<=offset)Erase(p->ch[0],k);
else Erase(p->ch[1],k-offset);
}
}初始化
顺带一提，从本函数开始是非工具函数（之前的都是protected，并非外部直接调用的函数）。
void init(){
tail=mempool;
null=tail++;
null->ch[0]=null->ch[1]=null;
null->cover=null->size=null->exist=0;
root=null;
bc_top=0;
}初始化就搞一个空节点，然后没了。
其他操作
这些操作都是建立在工具函数的基础上，YY出来的。
要注意插入和删除都得检查树是否平衡。
然后查询rank和第K大都是循环实现，思路很朴实。
void insert(int val){
Node** res=Insert(root,val);
if(*res!=null)Rebuild(*res);
}
int rank(int val){
Node* now=root;
int ans=1;
while(now!=null){
if(now->val>=val)now=now->ch[0];
else{
ans+=now->ch[0]->size+now->exist;
now=now->ch[1];
}
}
return ans;
}
int kth(int val){
Node* now=root;
while(now!=null){
if(now->ch[0]->size+1==val&&now->exist)return now->val;
if(now->ch[0]->size>=val)now=now->ch[0];
else val-=now->ch[0]->size+now->exist,now=now->ch[1];
}
}
void erase(int k){
Erase(root,rank(k));
if(root->size<root->cover*alpha)Rebuild(root);
}代码
AC代码放心使用：
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
namespace Scapegoat{
const int N=100100;
const double alpha = 0.75;
struct Node{
int val,size,cover;
bool exist;
Node* ch[2];
void pushup(){this->size=ch[0]->size+ch[1]->size+(int)exist,this->cover=ch[0]->cover+ch[1]->cover+1;}
int isbad(){return (ch[0]->cover>this->cover*alpha+5)||(ch[1]->cover>this->cover*alpha+5);}
};
struct Tree{
protected:
Node mempool[N];
Node *tail,*null,*root;
Node *bc[N];
int bc_top;
Node* newNode(int val){
Node* p=bc_top?bc[--bc_top]:tail++;
p->ch[0]=p->ch[1]=null;
p->size=p->cover=p->exist=1;
p->val=val;
return p;
}
void Travel(Node* p,vector<Node*>& x){
if(p==null)return;
Travel(p->ch[0],x);
if(p->exist)x.push_back(p);
else bc[bc_top++]=p;
Travel(p->ch[1],x);
}
Node* Divide(vector<Node*>& x,int l,int r){
if(l>=r)return null;
int mid=(l+r)>>1;
Node* p=x[mid];
p->ch[0]=Divide(x,l,mid);
p->ch[1]=Divide(x,mid+1,r);
p->pushup();
return p;
}
void Rebuild(Node*& p){
static vector<Node*> x;
x.clear();
Travel(p,x);
p=Divide(x,0,x.size());
}
Node** Insert(Node*& p,int val){
if(p==null){
p=newNode(val);
return &null;
}
p->size++,p->cover++;
Node** res=Insert(p->ch[val>=p->val],val);
if(p->isbad())res=&p;
return res;
}
void Erase(Node*& p,int k){
p->size--;
int offset=p->ch[0]->size+p->exist;
if(p->exist&&offset==k){
p->exist=false;
}else{
if(k<=offset)Erase(p->ch[0],k);
else Erase(p->ch[1],k-offset);
}
}
public:
void init(){
tail=mempool;
null=tail++;
null->ch[0]=null->ch[1]=null;
null->cover=null->size=null->exist=0;
root=null;
bc_top=0;
}
Tree(){
init();
}
void insert(int val){
Node** res=Insert(root,val);
if(*res!=null)Rebuild(*res);
}
int rank(int val){
Node* now=root;
int ans=1;
while(now!=null){
if(now->val>=val)now=now->ch[0];
else{
ans+=now->ch[0]->size+now->exist;
now=now->ch[1];
}
}
return ans;
}
int kth(int val){
Node* now=root;
while(now!=null){
if(now->ch[0]->size+1==val&&now->exist)return now->val;
if(now->ch[0]->size>=val)now=now->ch[0];
else val-=now->ch[0]->size+now->exist,now=now->ch[1];
}
}
void erase(int k){
Erase(root,rank(k));
if(root->size<root->cover*alpha)Rebuild(root);
}
};
}
using namespace Scapegoat;
Tree tree;
int main(){
int n,op,x;
scanf("%d",&n);
while(n--){
scanf("%d%d",&op,&x);
if(op==1)tree.insert(x);
if(op==2)tree.erase(x);
if(op==3)printf("%d\n",tree.rank(x));
if(op==4)printf("%d\n",tree.kth(x));
if(op==5)printf("%d\n",tree.kth(tree.rank(x)-1));
if(op==6)printf("%d\n",tree.kth(tree.rank(x+1)));
}
return 0;
}然后就没了。
后记
有一天我一个ZZ同学跟我说替罪羊树乃至平衡树提高组不考。
o_0??WTF?????????