平衡树

fhq treap(无旋treap)
treap:其中每个点有输入值与随机值两种值,输入值满足二叉树性质,随机值满足堆性质。
而fhq如何实现平衡呢
它需要两个操作:分裂与合并

分裂:

目的:将其分成所有权值都大于或小于等于某一值的两棵平衡树
我们现在需要两个指针,每一次走到该点权值是否大于该值的反方向

点击查看代码
//pushup()一般是用来更改每一点的size...
void split(int &a,int &b,int p){
	if(p==0){
		a=b=0;
		pushup(p);
		return ;
	}
	if(e[p].sm<=val){//此处val为进行分离的那一个值
		a=p;
		split(e[p].r,b,e[p].r);
	}
	else{
		b=p;
		split(a,e[p].l,e[p].l);
	}
	pushup(p);
}
上一篇:[转]Oracle DB 备份和恢复的概念


下一篇:fhq_treap