分步讲解平衡树--最强版

今天想告诉大家

Winner Never Quit

我从上午11点写到晚上9点  靠的就是这句话让我深刻理解了平衡树

那我们开始吧

二叉排序树 

二叉排序树是一种很万能的东西，它通过使二叉树的中序遍历为升序来维护一个可插入删除和查询许多信息的序列。具体地，对于插入操作，从根节点开始搜索，对于比根节点小的数，递归它的左子树，对于比根节点大的数，递归它的右子树，知道搜索到一个空位就把这个数塞进去。但是，二叉排序树有一个很致命的地方，由于递归的复杂度是O(深度)的，而树型只要插入序列给定了就确定了，深度可能非常之大，比如给一串升序的数字，显然树会退化成一条链，这样以来，复杂度就完全不靠谱，对于大数据完全会超时，平衡树就是在二叉排序树的基础上通过一些操作来使二叉排序树平衡，也就是使它深度接近logn。 

平衡树就是做了手术的二叉树

它支持

1. 插入 x 数
2. 删除 x数(若有多个相同的数，因只删除一个)
3. 查询 x数的排名(排名定义为比当前数小的数的个数 +1 。若有多个相同的数，因输出最小的排名)
4. 查询排名为 x 的数
5. 求 x 的前驱(前驱定义为小于 xx ，且最大的数)
6. 求 x 的后继(后继定义为大于 xx ，且最小的数)

首先,数组就不能出差错

struct Node{
	int l;//左右儿子  
        int r;
	int v;//它的值
	int f;//优先值 --> 满足堆的性质
	int s;//包括自己和子树中元素的个数 
	int num;//与根的值相同元素个数 
}tr[N];//开到n就够了哟
           

接下来,得学会左旋与右旋(做手术)

 以右旋为例

首先,令根P的左儿子为K

int k=tr[p].l;
           

其次,K的右儿子变成P的左儿子

然后,发现现在的K的所有元素其实就是刚才的P的所有元素

于是

tr[k].s=tr[p].s
           

那P的所有元素呢

update(p)
void update(int o){
	tr[o].s=tr[o].num+tr[tr[o].l].s+tr[tr[o].r].s;
    //左右元素+与tr[o].v重复的个数
}
           

最后不要忘了 

p=k
           

因为新的根是k了

插入(insert)

void insert(int &o,int v){
	if(o==0){//1
		o=++tot;
		tr[o].s=tr[o].num=1,tr[o].v=v,tr[o].f=randon();
		return;
	}
	tr[o].s++;//2
	if(tr[o].v==v) tr[o].num++;//若相等,num++,就不往下插了 
	else if(v<tr[o].v){//小的在左边,大的在右边//3
		insert(tr[o].l,v);
		if(tr[tr[o].l].f<tr[o].f) right(o);//如果新插的必他爸的优先值小//4
		//就不满足堆的性质,所以右旋把它搞上去
	}
	else{
		insert(tr[o].r,v);
		if(tr[tr[o].r].f<tr[o].f) left(o);
	}
}
           

代码里面有4个点

1.如果当前节点是空的,就插入

randon是自定义的随记函数

2.节点个数肯定要加一,如果跟当前节点相等,就不往下插,相等的数(num)++就好了

3.左小右大

4.熟悉左右旋

右就是根往右边降

删除(erase)

相当于做手术将肿瘤切除

但肿瘤藏在身体内部,要把它搞到外面来才好切

void erase(int &o,int v){
	if(o==0) return;
}
           

如果当前节点就是要找的值

if(v==tr[o].v){//找到了删除的点 
		if(tr[o].num>1){
			tr[o].num--,tr[o].s--,return;
		}
	}
           

又是num!?

因为只用删除一个,把num--就好,也不用向下找了

如果有一个节点空了,另一个就做根呗,相当于直接被自己另一个儿子覆盖

if(!tr[o].l) o=tr[o].r;
else if(!tr[o].r) o=tr[o].l;
           

现在要想办法搞到外面去,就要不停地做小手术

注意这里的o已经是新的o了,就是刚刚转上来的

else{
	if(tr[tr[o].l].f<tr[tr[o].r].f){//因为要满足堆的性质,只能小的来做根 
		right(o),erase(o,v);
	}
	else left(o),erase(o,v);
} 
           

如果还没有找到肿瘤,就根据肿瘤大小慢慢找

else if(v<tr[o].v) tr[o].s--,erase(tr[o].l,v);
else tr[o].s--,erase(tr[o].r,v);
           

查x的排名(quary_back)

节点为空,返回0

if(o==0)return 0;
           

如果刚好找到x,排名就是左边比它小的+1

if(tr[o].v==v) return tr[tr[o].l].s+1;
           

左小右大

else if(x<tr[o].v){//找左 
		return quary_rank(tr[o].l,v);
	}
	else{
		return tr[tr[o].l].s+tr[o].num+quary_rank(tr[o].r,v);
	}
           

注意右边,首先比左边所有都大,然后比根节点的num个大

查排名为x的(quary_num)

不说了,一张图搞定

int quary_num(int o,int v){
	if(o==0) return 0;
	if(v<tr[o].s){//肯定在左边
		return quary_num(tr[o].l,v); 
	}
	else if(x>tr[o].num+tr[tr[o].l].s){//肯定在右边 
		return quary_num(tr[o].r,v-tr[tr[o].l].s) 
	}
	else return tr[o].v;
}
           

查x的前驱(quary_pre)

主要的思想为

还可以变大就遍历右子树,而且右子树任何一个答案都可以比当前根大,所以ans直接更新

void quary_pre(int o,int v){
	if(o==0) return;
	if(v>tr[o].v){//还可以更大,这个根可能为答案 
		ans=o,quary_pre(tr[o].r,v); 
	}
	else quary_pre(tr[o].l,v);
} 
           

查x的后继(quary_sub)

跟上面差不多

void quary_sub(int o,int v){
	if(o==0) return;
	if(v<tr[o].v){//还可以更小, 这个根可能为答案 
		ans=o,quary_sub(tr[o].l,v); 
	} 
	else quary_sub(tr[o].r,v);
} 
           

你是否发现,有些是 int &o 有些是int o

其实int &o 的root会跟着变,什么意思呢

就是这一层过后,我们的全局变量root会变,这样也就保证了root始终是最上面的

当然,查询等操作,不会改变root 也就不用&了

代码

#include<bits/stdc++.h>
#define N 100005
using namespace std;
struct Node{
	int l,r,v,s,f,num;
}tr[N];
int n,root,ans,tot;
int read(){
	int cnt=0;char ch=0;
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))cnt=cnt*10+(ch-'0'),ch=getchar();
	return cnt;
}
inline int randon(){
	static int seed=233;
	return seed=int(seed*47821LL%2147483647);
}
void update(int o){
	tr[o].s=tr[o].num+tr[tr[o].l].s+tr[tr[o].r].s;
}
void right(int &o){
	int k=tr[o].l;
	tr[o].l=tr[k].r,tr[k].r=o;
	tr[k].s=tr[o].s,update(o);
	o=k;
}
void left(int &o){
	int k=tr[o].r;
	tr[o].r=tr[k].l,tr[k].l=o;
	tr[k].s=tr[o].s,update(o);
	o=k;
}
void insert(int &o,int v){
	if(o==0){
		o=++tot;
		tr[o].s=tr[o].num=1,tr[o].v=v,tr[o].f=randon();
		return;
	}
	tr[o].s++;
	if(tr[o].v==v) tr[o].num++;//若相等,num++,就不往下插了 
	else if(v<tr[o].v){//小的在左边,大的在右边 
		insert(tr[o].l,v);
		if(tr[tr[o].l].f<tr[o].f) right(o);//如果新插的必他爸的优先值小
		//就不满足堆的性质,所以右旋把它搞上去
	}
	else{
		insert(tr[o].r,v);
		if(tr[tr[o].r].f<tr[o].f) left(o);
	}
}
void erase(int &o,int v){
	if(o==0) return;
	if(v==tr[o].v){//找到了删除的点 
		if(tr[o].num>1){
			tr[o].num--,tr[o].s--;
			return;
		}
		if(!tr[o].l) o=tr[o].r;
		else if(!tr[o].r) o=tr[o].l;
		else{
			if(tr[tr[o].l].f<tr[tr[o].r].f){//因为要满足堆的性质,只能小的来做根 
				right(o),erase(o,v);
			}
			else left(o),erase(o,v);
		} 
	}
	else if(v<tr[o].v) tr[o].s--,erase(tr[o].l,v);
	else tr[o].s--,erase(tr[o].r,v);
}
int quary_rank(int o,int v){
	if(o==0) return 0;
	if(tr[o].v==v) return tr[tr[o].l].s+1;
	else if(v<tr[o].v){//找左 
		return quary_rank(tr[o].l,v);
	}
	else{
		return tr[tr[o].l].s+tr[o].num+quary_rank(tr[o].r,v);
	}
}
int quary_num(int o,int v){
	if(o==0) return 0;
	if(v<=tr[tr[o].l].s){//肯定在左边
		return quary_num(tr[o].l,v); 
	}
	else if(v>tr[o].num+tr[tr[o].l].s){//肯定在右边 
		return quary_num(tr[o].r,v-tr[tr[o].l].s-tr[o].num);
	}
	else return tr[o].v;
}
void quary_pre(int o,int v){
	if(o==0) return;
	if(v>tr[o].v){//还可以更大,这个根可能为答案 
		ans=o,quary_pre(tr[o].r,v); 
	}
	else quary_pre(tr[o].l,v);
} 
void quary_sub(int o,int v){
	if(o==0) return;
	if(v<tr[o].v){//还可以更小, 这个根可能为答案 
		ans=o,quary_sub(tr[o].l,v); 
	} 
	else quary_sub(tr[o].r,v);
} 
int main(){
	n=read();
	for(int i=1;i<=n;i++){
		int op=read(),x=read();
		if(op==1) insert(root,x);
		if(op==2) erase(root,x);
		if(op==3) cout<<quary_rank(root,x)<<endl;
		if(op==4) cout<<quary_num(root,x)<<endl;
		if(op==5) quary_pre(root,x),cout<<tr[ans].v<<endl;
		if(op==6) quary_sub(root,x),cout<<tr[ans].v<<endl;
	}
	return 0;
}