学习笔记:二叉平衡树之 fhp-treap

管理员

问题背景:

你需要维护一个整数集合,可以满足一下几种操作:

  1. 插入一个整数 xx。

  2. 删除一个整数 xx(若有多个相同的数,只删除一个)。

  3. 查询整数 xx 的排名(排名定义为比当前数小的数的个数 +1+1)。

  4. 查询排名为 xx 的数(如果不存在,则认为是排名小于 xx 的最大数。保证 xx 不会超过当前数据结构中数的总数)。

  5. 求 xx 的前驱(前驱定义为小于 xx,且最大的数)。

  6. 求 xx 的后继(后继定义为大于 xx,且最小的数)。

这时候其实有很多种办法:权值线段树set 等都可以维护。

我们选择用 fhp-treap 来做

算法目的

我们都知道二叉排序树可能会退化为(O(n)),是因为当他的结构为链的时候深度超级大

我们想办法让他的深度最多只有(O(logn)),这样我们就可以用(O(logn))的时间内进行操作

现在我们就弄了一个东西叫做树堆

treap=tree+heap

实现方式

大致思想

给每个东西随机化一下,让他既满足排序树的性质,又满足堆的性质,用随机来优化深度

我们定义两个操作:treap的合并让treap<=x的部分分离

具体实现

首先考虑我们有这两个操作怎么样能够满足上面那六种情况

1. 插入某一个数x:ins(x)

我们把小于等于x的子树从大树中分离,得到左边的是t1,右边的是t2

接着,我们把插入的这个点定为x,合并t1和x,再合并前面的和t2

2. 删除一个数x:del(x)

(≤x-1)的树分离,得到左边的t1和右边的t2,然后再把t2中(≤x)的树分离,得到t3(全为x)和t2。
因为删除的数可能有很多个,我们只能删一个,我们就考虑删除t3的堆顶,即把t3的左子树t4和t3的右子树t5独立开来,把t1和t4合并,t5和t2合并,最后两个再同时合并,就可以得到一个没有t3(此时只有一个x)的treap了

3. 查找x的排名:get_rank(x);

首先我们需要把(≤x-1)的子树分离出来,在查询他们的节点个数,然后合并就行了。
最后答案就是节点个数+1

tips:由于需要记录节点个数,因此还需要有一个sum和push_up

4. 查找排名为x的值:get_data(fx,x);

从树顶开始遍历即可,由大小决定走左边还是右边或者现在就返回
与线段树二分类似

5. 找x的前驱 get_pri(x);

(≤x-1)的子树get_data他的大小(能找到他最右边的)

6. 找x的后继 get_suf(x);

把>x的子树get_data(1)(能找到他最左边的)

我们就能够知道,结构体需要定义的东西和push_up:

struct node {
	int val;//键值
	int pri;//优先级,即开始会给他一个rand让他随机调整
	int sum;//子树大小
	int ls,rs;//左儿子右儿子
}d[N];
//......
void push_up(int id) {
	d[id].sum=d[d[id].ls].sum+d[d[id].rs].sum+1;//加一不能忘
}

然后考虑怎样写split和merge


1. split

因为现在优先级是正确的,上面的优先级一定比现在的大,只要符合是上面的连向下面的就符合优先级的性质了,那么只需要考虑值的大小分裂

  1. 如果id=0,即已经分完了,返回

  2. 如果此时 $ id->val ≤x $ id和左边的一定都在左子树里面,此时只需分裂右子树,左子树的根l=id,l的右子树r 递归找

  3. 如果此时 $ id->val >x $ id和右边的一定都在右子树里面,此时只需分裂左子树,右子树的根r=id,lr的左子树 递归找

左子树不断地想填右边,右子树不断地想填左边

void split(int id,int x,int &l,int &r){
	//l,r引用的是两个子树的根
	if(id==0) {
		l=0;r=0;return ;
	}
	if(d[id].val<=x) {
		l=id;
		split(d[id].rs,x,d[id].rs,r);
		//顺序千万不能搞反,否则你调大半天不知道啥问题
	} else {
		r=id;
		split(d[id].ls,x,l,d[id].ls);
	}
	push_up(id);
	//一定要记得跟新他的sum,
	//为什么只需要更新一个呢,因为另一个在下一层递归中已经被更新了
}

2. merge(与split对称不知这样表述对不对

因为现在l值一定小于r值是正确的,只要不改变对于两棵树树内部的相对大小关系(即合并完原来的左边的一定在右边的,那我们就只需要考虑优先级了

  1. 如果id=0,即已经分完了,返回

  2. 同理,谁的优先级小(小根堆)那就谁做老大,并相应的保留左子树和右子树(值就能不受改动),在递归他未确定的部分和另一棵子树

左子树不断地保留左边,右子树不断地保留右边//因为左边右边分别比上面的小和大

int merge(int l,int r) {
	if(!l||!r) return l+r;
	if(d[l].pri<d[r].pri) {
		d[l].rs=merge(d[l].rs,r);//注意顺序
		push_up(l);
		return l;
	} else {
		d[r].ls=merge(l,d[r].ls);//注意顺序,最好画个图推一下
		push_up(r);
		return r;
	}
}

然后通过整理,我们就能够造出这样一种数据结构满足上述要求了:

代码实现细节:

void ins(int x) {
	int t1=0,t2=0,t=0;//注意初值
	d[++cnt].val=x;
	d[cnt].sum=1;
	d[cnt].pri=rand();
	t=cnt;
	split(fx,x,t1,t2);//注意顺序
	fx=merge(merge(t1,t),t2);//每次合并一定要记录新的根
}

void del(int x) {
	int t1=0,t2=0,t3=0,t4=0,t5=0;//t3 will be deleted
	split(fx,x-1,t1,t2);
	split(t2,x,t3,t2);
	t4=d[t3].ls;t5=d[t3].rs;
	fx=merge(merge(t1,t4),merge(t5,t2));
	d[t3].val=-1;
}

int get_rank(int x) {
	int t1=0,t2=0,ans=0;
	split(fx,x-1,t1,t2);
	ans=d[t1].sum+1;
	fx=merge(t1,t2);
	return ans;
}

int get_data(int num,int x) {
	if(d[d[num].ls].sum+1==x) return d[num].val;
	if(d[d[num].ls].sum>=x) return get_data(d[num].ls,x);
	else return get_data(d[num].rs,x-d[d[num].ls].sum-1);
}

int get_pri(int x) {
	int t1=0,t2=0,ans=0;
	split(fx,x-1,t1,t2);
	ans=get_data(t1,d[t1].sum);
	fx=merge(t1,t2);
	return ans;
}

int get_suf(int x) {
	int t1=0,t2=0,ans=0;
	split(fx,x,t1,t2);
	ans=get_data(t2,1);
	fx=merge(t1,t2);
	return ans;
}

这样,我们就完成了这种数据结构