替罪羊树
上一篇：平衡树学习笔记（3）-------Splay
替罪羊树可以说是最暴力的平衡树
但却跑的很快
有多暴力？
不是一条链影响复杂度吗？
暴力给你拍到一个vector里去（没错，整棵树暴力拍扁）
再重新建树，建出的树像线段树那样二分建来保证平衡
可谓是要多暴力有多暴力
在树套树上也有一些优势
(color{#9900ff}{定义})
const double eps=0.75;
struct node
{
int val,siz,cov;
bool exist;
node *ch[2];
void upd()
{
siz=ch[0]->siz+ch[1]->siz+exist;
cov=ch[0]->cov+ch[1]->cov+1;
}
bool nb(){ return ((ch[0]->cov>cov*eps+5)||(ch[1]->cov>cov*eps+5)); }
int rk() { return ch[0]->siz+exist;}
};
不同的是，替罪羊树的删除不是真正的删除，只是打个标记罢了
但是，要注意的是，如果被标记（假装删除）的点在某个子树中，而现在要把那个子树拍扁
则这个点就是真的被删除了qwq，重构的时候就不再把它加入新树了，因为没必要qwq
所以，val记录权值，siz记录实际大小，cov记录节点个数
exist就是标记，判断此节点是否存在
刚刚说它维护平衡的方式就是拍扁重构
但总不能每次都把所有拍扁重构
条件就是，左/右子树大小大于自己大小*平衡因子
这个平衡因子也是比较玄学，一般在0.7---0.85即可吧qwq
nb的意思是。。。need-bong，判断是否需要拍扁，不，是被拍扁QAQ
(color{#9900ff}{基本操作})
1、travel
travel，顾名思义，旅行
让树上的节点去vector旅行qwq（<-----瞎bb）
说难听点就是被拍扁。。。。。。
不过，为了重构便捷，还记得第一节说的吗
平衡树的中序遍历可是有序的！
所以，按照中序遍历拍扁，就方便重构了qwq
//vector要传地址（别告诉我不知道为什么）
void travel(nod o,vector<nod> &v)
{
//到空节点不用管
if(o==null) return;
//中序遍历左根右
travel(o->ch[0],v);
//放进vector之前，判断是否存在， 不存在就不用管了，真正意义上把它删除
if(o->exist) v.push_back(o);
//else这一行各位数组dalao可以忽略，它的左右就是回收删的节点放入内存池，节省空间利用
else ts[top++]=o;
travel(o->ch[1],v);
}
2、divide
别问我为啥叫divide，也许是因为二分建树吧qwq
nod divide(vector<nod> &v,int l,int r)
{
//二分边界（因为[l,r)左闭右开）
if(l>=r) return null;
int mid=(l+r)>>1;
//mid给自己，[l,mid-1]给左孩子，[mid+1,r)给右孩子
nod o=v[mid];
o->ch[0]=divide(v,l,mid);
o->ch[1]=divide(v,mid+1,r);
//别忘维护性质
o->upd();
return o;
}
3、rebuild
这就是重构，说白了就是把前两个联系在一起
void rebuild(nod &o)
{
static vector<nod> v;
v.clear();
travel(o,v);
//左闭右开不要忘
o=divide(v,0,v.size());
}
基本操作已经完成，够暴力吧qwq
(color{#9900ff}{其它操作})
1、插入
由于涉及递归，而且有些不同，所以分成了两个函数来写
插入节点毕竟会改变树的样子
所以要考虑拍扁
那么，现在问题来了
我们既要保证树的平衡，又要保证复杂度，怎么办呢？
我们找满足nb的最浅的那个重构
这样既可以保证树的平衡，又不会因为太浅而影响复杂度（完美؏؏☝ᖗ乛◡乛ᖘ☝؏؏）
//返回的是最浅的nb（牛逼）点的地址
nod *ins(nod &o,int k)
{
if(o==null)
{
//如果为空则建立新节点
//注意返回的是指针的地址
o=newnode(k);
return &null;
}
//插入的点在当前点的子树内
//而这个点是存在的
//所以siz和cov都++
o->siz++,o->cov++;
//递归像某个子树找
nod *p=ins(o->ch[k>=o->val],k);
//先让p等于子树中的nb点
//如果当前点是nb点，显然o比p浅，所以p=&o
if(o->nb()) p=&o;
return p;
}
void ins(int k)
{
nod *p=ins(root,k);
//只要不空说明有nb点，就拍扁重构
if(*p!=null) rebuild(*p);
}
2、删除
因为我们只有拍扁重构的操作
对于删除实在是不方便
所以改了一下删除的方式
改成删除第k大
所以删除还得借助rnk qwq
//删除第k大的点
void del(nod &o,int k)
{
//沿途siz--，但cov不减，因为是假装删除qwq
o->siz--;
//如果当前点存在并且就是要删的点，就删了好了qwq
if(o->exist&&o->rk()==k) o->exist=false;
else if(k<=o->rk()) del(o->ch[0],k);
else del(o->ch[1],k-o->rk());
//否则向该去的方向递归，注意k的变化
}
//下面是删k这个数，通过rnk获取排名
void del(int k)
{
del(root,rnk(k));
//判断是否需要重构
if(root->siz<root->cov*eps) rebuild(root);
}
3、查询数x的排名
这个不解释了，比Splay的要简单不少了
int rnk(int k)
{
nod o=root;
int rank=1;
while(o!=null)
{
if(o->val>=k) o=o->ch[0];
else rank+=o->rk(),o=o->ch[1];
}
return rank;
}
4、查询第k大的数
这个也差不多，平衡树都是相通的qwq
唯一要注意的是，因为被删除的点有些是假装被删除的，所以要判断
int kth(int k)
{
nod o=root;
while(o!=null)
{
if(o->ch[0]->siz+1==k&&o->exist) return o->val;
else if(o->ch[0]->siz>=k) o=o->ch[0];
else k-=o->rk(),o=o->ch[1];
}
}
5,6、前驱，后继
直接用rnk和kth嵌套就行了
放上完整代码
#include<cstdio>
#include<queue>
#include<vector>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<cmath>
#define _ 0
#define LL long long
#define Space putchar(' ')
#define Enter putchar('
')
#define fuu(x,y,z) for(int x=(y);x<=(z);x++)
#define fu(x,y,z) for(int x=(y);x<(z);x++)
#define fdd(x,y,z) for(int x=(y);x>=(z);x--)
#define fd(x,y,z) for(int x=(y);x>(z);x--)
#define mem(x,y) memset(x,y,sizeof(x))
#ifndef olinr
char getc()
{
static char buf[100001],*p1=buf,*p2=buf;
return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100001,stdin),p1==p2)? EOF:*p1++;
}
#else
#define getc() getchar()
#endif
template<typename T> void in(T &x)
{
int f=1; char ch; x=0;
while(!isdigit(ch=getc()))(ch=='-')&&(f=-f);
while(isdigit(ch)) x=x*10+(ch^48),ch=getc();
x*=f;
}
const double eps=0.75;
struct node
{
int val,siz,cov;
bool exist;
node *ch[2];
void upd()
{
siz=ch[0]->siz+ch[1]->siz+exist;
cov=ch[0]->cov+ch[1]->cov+1;
}
bool nb(){ return ((ch[0]->cov>cov*eps+5)||(ch[1]->cov>cov*eps+5)); }
int rk() { return ch[0]->siz+exist;}
};
typedef node* nod;
node st[1050500],*ts[1050500];
nod tail=st,root,null;
int top,n;
using std::vector;
nod newnode(int k)
{
nod o=top? ts[--top]:tail++;
o->ch[0]=o->ch[1]=null;
o->cov=o->siz=o->exist=1;
o->val=k;
return o;
}
void travel(nod o,vector<nod> &v)
{
if(o==null) return;
travel(o->ch[0],v);
if(o->exist) v.push_back(o);
else ts[top++]=o;
travel(o->ch[1],v);
}
nod divide(vector<nod> &v,int l,int r)
{
if(l>=r) return null;
int mid=(l+r)>>1;
nod o=v[mid];
o->ch[0]=divide(v,l,mid);
o->ch[1]=divide(v,mid+1,r);
o->upd();
return o;
}
void rebuild(nod &o)
{
static vector<nod> v;
v.clear();
travel(o,v);
o=divide(v,0,v.size());
}
nod *ins(nod &o,int k)
{
if(o==null)
{
o=newnode(k);
return &null;
}
o->siz++,o->cov++;
nod *p=ins(o->ch[k>=o->val],k);
if(o->nb()) p=&o;
return p;
}
void del(nod &o,int k)
{
o->siz--;
if(o->exist&&o->rk()==k) o->exist=false;
else if(k<=o->rk()) del(o->ch[0],k);
else del(o->ch[1],k-o->rk());
}
void init()
{
null=tail++;
null->ch[0]=null->ch[1]=null;
null->siz=null->cov=null->val=0;
root=null;
}
void ins(int k)
{
nod *p=ins(root,k);
if(*p!=null) rebuild(*p);
}
int rnk(int k)
{
nod o=root;
int rank=1;
while(o!=null)
{
if(o->val>=k) o=o->ch[0];
else rank+=o->rk(),o=o->ch[1];
}
return rank;
}
int kth(int k)
{
nod o=root;
while(o!=null)
{
if(o->ch[0]->siz+1==k&&o->exist) return o->val;
else if(o->ch[0]->siz>=k) o=o->ch[0];
else k-=o->rk(),o=o->ch[1];
}
}
void del(int k)
{
del(root,rnk(k));
if(root->siz<root->cov*eps) rebuild(root);
}
int main()
{
init();
in(n);
int p,x;
while(n--)
{
in(p),in(x);
if(p==1) ins(x);
if(p==2) del(x);
if(p==3) printf("%d
",rnk(x));
if(p==4) printf("%d
",kth(x));
if(p==5) printf("%d
",kth(rnk(x)-1));
if(p==6) printf("%d
",kth(rnk(x+1)));
}
return ~~(0^_^0);
}
下一篇：平衡树学习笔记（5）-------SBT