FHQ-Treap

模板传送
FHQ-Treap顾名思义就是范浩强大佬设计的一种二叉平衡树
下面我们来讲一下它的原理和代码

结构体

对于一个节点,我们需要记录的是

  • 对应的值
  • 子树节点数
  • 左右孩子编号
  • 对应的随机值
struct str{
	int val,size,l,r,key;
}fhq[100005];

看到这里有人疑惑了,这个对应的随机值是怎么回事啊?
这里就涉及到了一个FHQ-Treap里优化的一个小技巧
我们知道,树在最坏的情况下,会退化成一条链
但很显然,出于时间复杂度上来讲,我们并不希望它成为一条链,因为我们的遍历是按照一层一层来遍历的,如果退化成一条链就会从最优O(log n)的复杂度直接降到O( n ),所以我们就用这个随机的值去让这个二叉树变得平衡,具体怎么去使用这个随机值的请看函数merge

函数

首先,先给大家把主要使用的函数列出来,然后我们再一个一个讲

void update(int x)
void split(int now,int dat,int &x,int &y)
int merge(int x,int y)
int add(int dat)
void ins(int dat)
void del(int dat)
int get_rk(int dat)
int get_num(int dat)
void get_pre(int dat)
void get_next(int dat)

看起来是不是很让人头晕眼花?
我们把函数要具体实现什么注释一下:

void update(int x)//更新数据
void split(int now,int dat,int &x,int &y)//分裂
int merge(int x,int y)//合并
int add(int dat)//在树里添加节点(实际的操作)
void ins(int dat)//节点进树(与上一个要区分开,这个只是一个输入的对接)
void del(int dat)//节点出树
int get_rk(int dat)//求dat数的排名
int get_num(int dat)//求排dat名的数
void get_pre(int dat)//求前驱
void get_next(int dat)//求后继

铺垫的差不多了,是时候开始讲了

update

update函数十分简单,主要要求实现的是更新该节点的子树长度,因为我们会在树上进行其他的修改操作,长度很可能会随之变化,所以这个函数一定是要放在第一位写的

void update(int x){//要更新x节点
	fhq[x].size=fhq[fhq[x].l].size+fhq[fhq[x].r].size+1;
 //子树节点数=左子树节点数+右子树节点数+本身;
	return ;
}

split

这个函数是FHQ-Treap的重点之一,主要实现的是把一棵树拆成两棵树方便后续操作,我们先解释一下这里的参数都是什么意思

void split(int now,int dat,int &x,int &y)
//now表示现在遍历到了哪个节点,dat是要从哪里拆开这棵树,x和y是拆后两颗树的根节点

因为x和y的值在函数里会被不停地更新,所以我们这里的&x,&y就尤为重要
第一步,根据二叉搜索树,找到从哪里分成两半

if(dat<fhq[now].val)//如果小,那就在now的左子树里
	{
	y=now;//把y的值更新,缩小范围
	split(fhq[now].l,dat,x,fhq[now].l);
	}else{//如果不小,那就在now的右子树里
	x=now;//把x的值更新,缩小范围
	split(fhq[now].r,dat,fhq[now].r,y);
	}

(如果看不懂的话可以自己画个图理解一下,本人能力有限,不会做动图)
最后,我们就会把分裂出来的两棵树的根节点求出来
你以为这样就完了吗?还要注意几个细节
递归跳出:

if(now==0){
	x=y=0;
	return ;
}

还有!你已经修改了这棵树了,别忘了更新!!!

update(now);

merge

来到第二个重点,也是有很多人包括刚学的我非常不理解的地方————合并函数
还是先解释参数

int merge(int x,int y)//将以x为根的树和以y为根的树合并

它到底是怎么用这些随机值来保持平衡的呢?
我们来看一个问题:现在你有两棵二叉搜索树,并且告诉你一棵树的根节点x一定比另一颗树的根节点y要小,请问你能怎么组合?
聪明的你肯定会想到两种情况:

第一种是把x插进y的左子树里,第二种是把y插进x的右子树里

如果把这个问题交给聪明的你的话,你一定会选择尽可能平衡的一种做法来合并,但很可惜,计算机并没有你那么聪明的脑子,它只会机械的执行一种操作,而这种操作执行下去就会逐渐变成一条链,怎么办呢?
这时候我们的随机值就发挥出用场了,当面对于这样的两难抉择中,它就不会再去考虑x和y的值,不会去考虑这棵二叉平衡树(因为很显然,前者没必要,给你的时候就知道x小y大,后者不用管,因为怎样操作都是一棵二叉平衡树),而是去维护堆

注意!我在这里是维护的小根堆!

如果我们x的key要小于y的key的话,根据小根堆我们就要把它合并到y的左子树中

如果我们y的key要小于x的key的话,根据小根堆我们就要把它合并到x的右子树中

(强迫症满意地笑了)
这样,我们就通过这些小小的随机值完美的解决了这个难题,维护了二叉搜索树的平衡
代码如下

if(fhq[x].key<=fhq[y].key){
	fhq[x].r=merge(fhq[x].r,y);//y插进x的右子树
	update(x);//别忘更新!我爱更新!警钟长鸣!这个代码第一次的bug就是忘更新了
	return x;//返回的是合并后的根节点
	}else{
	fhq[y].l=merge(x,fhq[y].l);//x插进y的左子树
	update(y);//别忘更新!我爱更新!
	return y;
	}

别忘了递归的跳出~

if(x==0||y==0) return x+y;

add

这个函数相较于上两个来说就简单了
还是参数

int add(int dat)//添加一个值为dat的节点,返回该节点下标

我们只需要给它进行以下操作

fhq[++cnt].size=1;//cnt是这棵树的总节点数
fhq[cnt].key=rand(); //取随机值
fhq[cnt].val=dat;
return cnt;

OK力~

ins

解释参数

void ins(int dat)//插入一个dat进树

这里就很好玩了,我们的操作是这样
先通过dat值把这棵树劈成两半,此时一半<=dat,一半>dat

split(root,dat,x,y);//root是这棵树的根

传回来了两棵树的根节点后,我们把这个节点先悄悄的加进树里,此时相当于有三棵树存在

z=add(dat);

然后呢,我们要当老六,把这三棵树再组成一棵树

root=merge(merge(x,z),y);

这样,我们的添加节点操作就不可思议而且妙不可言的完成了!

del

与上一个函数相反,这个函数是删除操作

void del(int dat)//删除值为dat的一个节点

这个操作也很妙,集中注意力
我们先通过dat值把这棵树劈成两半,此时一半<=dat,一半>dat

split(root,dat,x,y);

然后和上面的思想差不多,我们再从<=dat的左树中再劈成两半,一半是=dat的节点,一半是其他节点

split(x,dat-1,x,z);//从左树根节点开始通过dat-1把左树劈成一半<=dat-1,一半=dat

然后呢,我们再把这个左树中的其他节点与右树一合并,一个dat就自然而然的被排挤出去了!

z=merge(fhq[z].l,fhq[z].r);//这里是重点!!!我们只需要删除一个dat而剩下的dat还是要再加回树里的!
root=merge(merge(x,z),y);//三块合并

这样这个操作也完成啦~

get_rk

这个函数是用来求值为dat的数的排名的
操作比上两个还要简单,我们通过dat值把这棵树劈成两半,此时一半<=dat,一半>dat,然后我们直接把左子树的节点数+1就是dat数的排名了~

split(root,dat-1,x,y);
int ans=fhq[x].size+1;
merge(x,y);//分裂完别忘了合并!
return ans;

get_num

这个函数的作用是求排名为dat的数值是多少
还是分类讨论的思想,我们发现这个排dat名的数要么在当前节点的左子树上,要么在当前节点的右子树上,要么就是当前节点,然后我们就可以写一个递归或循环来解决问题了(本人懒得写递归了,如果有递归强迫症可以自己写一下)

int now=root;//当前遍历到了哪个节点
while(now){
 if(fhq[fhq[now].l].size+1==dat){//就是当前节点
	 break;
	}
	else if(fhq[fhq[now].l].size>=dat)now=fhq[now].l;//在左子树里
	else{//在右子树里
	dat-=fhq[fhq[now].l].size+1;//注意!右子树比左子树都要大!所以求的时候一定要把左子树节点数减掉!
	now=fhq[now].r;
	}
}
return fhq[now].val;//华丽返回~

这样就又ok了

get_pre

一个求dat前驱的函数,操作起来也很妙
我们先通过dat-1把这棵树劈成两半,此时一半<dat,一半>=dat
然后我们就会发现,左子树中最大的那一个,就是dat的前驱
理解了意思,函数就好写了

split(root,dat-1,x,y);
int now=x;
while(fhq[now].r) now=fhq[now].r;//找左子树中最大的那一个,一定是最右的节点
cout<<fhq[now].val<<endl;
root = merge(x,y);//分裂完千万别忘了合并!

get_next

与上面的思想相同,但是这回我们要在右子树中找这个值:
我们先通过dat把这棵树劈成两半,此时一半<=dat,一半>dat
然后我们就会发现,右子树中最大的那一个,就是dat的后继

split(root,dat,x,y);
	int now=y;
	while(fhq[now].l) now=fhq[now].l;//找右子树中最小的那一个,一定是最左的节点
	cout<<fhq[now].val<<endl;
 root=merge(x, y);

实现

这样,我们就把所有的函数都捋了一遍,主函数也就好写了,以下是完整的AC代码

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<random>//这个里面有rand函数,必须写!
using namespace std;
int n;
int cnt;
int root;
struct str{
	int val,key,size,l,r;
}fhq[100005];
void update(int x){
	fhq[x].size=fhq[fhq[x].l].size+fhq[fhq[x].r].size+1;
	return ;
}
void split(int now,int dat,int &x,int &y){//分裂 
	if(now==0){
	x=y=0;
	return ;
	}
	if(dat<fhq[now].val)
	{
	y=now;
	split(fhq[now].l,dat,x,fhq[now].l);
	}else{
	x=now;
	split(fhq[now].r,dat,fhq[now].r,y);
	}
	update(now);
}
int merge(int x,int y){//合并,返回合并后的根 
	if(x==0||y==0) return x+y;
	if(fhq[x].key<=fhq[y].key){
	fhq[x].r=merge(fhq[x].r,y);
	update(x);
	return x;
	}else{
	fhq[y].l=merge(x,fhq[y].l);
	update(y);
	return y;
	}
}
int add(int dat){//增加结点 
	fhq[++cnt].size=1;
	fhq[cnt].key=rand();
	fhq[cnt].val=dat;
	return cnt;
}
void ins(int dat){//结点进树
	int x,y,z; 
	split(root,dat,x,y);
	z=add(dat);
	root=merge(merge(x,z),y);
	return ;
}
void del(int dat){//结点出树 
	int x,y,z; 
	split(root,dat,x,y);
	split(x,dat-1,x,z);
	z=merge(fhq[z].l,fhq[z].r);
	root=merge(merge(x,z),y);
}
int get_rk(int dat){//求dat数的排名 
	int x,y,z; 
	split(root,dat-1,x,y);
	int ans=fhq[x].size+1;
	merge(x,y);
	return ans;
} 
 
int get_num(int dat){//求排dat名的数
	int now=root;
	while(now){
 if(fhq[fhq[now].l].size+1==dat){
	break;
	}
	else if(fhq[fhq[now].l].size>=dat)now=fhq[now].l;
	else{
	dat-=fhq[fhq[now].l].size+1;
	now=fhq[now].r;
	}
	}
	return fhq[now].val;
}
void get_pre(int dat){//求前驱 
	int x,y,z; 
	split(root,dat-1,x,y);
	int now=x;
	while(fhq[now].r) now=fhq[now].r;
	cout<<fhq[now].val<<endl;
 root = merge(x,y);
}
void get_next(int dat){//求后继 
	int x,y,z; 
	split(root,dat,x,y);
	int now=y;
	while(fhq[now].l) now=fhq[now].l;
	cout<<fhq[now].val<<endl;
 root=merge(x, y);
}
int main(){
	cin>>n;
	while(n--){
	int opt,x;
	cin>>opt>>x;
	if(opt==1) ins(x);
	else if(opt==2) del(x);
	else if(opt==3) cout<<get_rk(x)<<endl;
	else if(opt==4) cout<<get_num(x)<<endl;
	else if(opt==5) get_pre(x);
	else get_next(x);
	}
	return 0;
}

好了,看到这里,想必你已经掌握了FHQ-Treap了,我们在下一个平衡树相见吧!

作者:鹈鹕灌顶原文地址:https://www.cnblogs.com/xuxiwen/p/17455085.html

%s 个评论

要回复文章请先登录注册