技术教程 编程教程 2021.12.06 平衡树——Treap 正文

2021.12.06 平衡树——Treap

2023-05-13,,

2021.12.06 平衡树——Treap

https://www.luogu.com.cn/blog/HOJQVFNA/qian-xi-treap-ping-heng-shu

1.二叉搜索树

1.1 性质

左子树的值都小于父节点，右子树的值都大于父节点。

2.堆

2.1 性质

是一颗完全二叉树，并且子节点不大于或小于父节点

3.Treap

一棵Treap上的节点有关键码和优先级。关键码满足二叉树的性质，优先级满足堆的性质。关键码就是真实的值，优先级 rand() 一个就成。

3.1 旋转rotate

为了满足关键码和优先级的顺序不变，也就是为了维护二叉搜索树和堆的性质，有大佬搞出了rotate这一操作。

3.1.1 右旋

就是把grandpa下降到右边，dad升到根节点。

旋转前：

旋转后：

3.1.2 左旋

就是把grandpa下降到左边，uncle升到根节点。

旋转前：

旋转后：

3.1.3 代码实现

我们可以发现每种旋转中只有两个节点的父节点变了。

如果是右旋，改变了cousin与grandpa：cousin是dad的右儿子，变为consin是grandpa的左儿子；dad的右儿子变成了grandpa。

如果是左旋，改变了son与grandpa：son是uncle的左儿子，变成了son是grandpa的右儿子；uncle的左儿子变成了grandpa。

改变的节点都与旋转的方向有关，所以左旋和右旋可以合并，写在一个函数中。

flag ：0 \(\longrightarrow\) 左旋，1 \(\longrightarrow\) 右旋

son[x][0/1] ：0 \(\longrightarrow\) 左儿子，1 \(\longrightarrow\) 右儿子

代码如下：

inline void rotate(int &x,int flag){

	int y=son[x][flag^1];

	int change=son[y][flag];

	son[x][flag^1]=change;

	son[y][flag]=x;

	update(x);

	update(y);

	x=y;

}

旋转完之后因为节点关系变化，记得更新dad和grandpa。

sizei[x] ：x节点为根节点所在子树大小

same[x] ：与x节点关键码大小相同的个数

代码如下：

inline void update(int x){

	sizei[x]=sizei[son[x][0]]+sizei[son[x][1]]+same[x];

}

3.2 插入insert

从根节点开始向下找。

val[x] ：x节点关键码大小

key ：x节点优先级大小

root ：根节点

cnt ：当前Treap中结点的个数

vali ：被插入的关键码的值

如果cnt==0 ，新建节点，返回 ，不用更新（就孤零零的一个节点更新个啥？）；

如果 val[x]==vali ，只更新 sizei[x] 与 same[x] 的值，加一；

否则，继续插入，直到满足以上两个情况，如果被更新的子树的优先级大于x的优先级，向反方向旋转。

（旋转吧，小陀螺~——来自蔡明小品）

代码如下：

inline void insert(int &x,int vali){

	if(!x){

		x=++cnt;

		sizei[x]=same[x]=1;

		val[x]=vali;

		key[x]=rand();

		return ;

	}

	if(val[x]==vali)return (void)(++sizei[x],++same[x]);

	int flag=vali>val[x];

	insert(son[x][flag],vali);

	if(key[x]<key[son[x][flag]])rotate(x,flag^1);

	update(x);

}

温馨提示：记得更新。

3.3 删除deletei

vali ：被删除的关键码的值

如果 val[x]==vali ：

如果没有左儿子也没有右儿子，同insert正好相反，更新 sizei[x] 与 same[x] 的值，减一。如果这个节点被删空了，删除这个节点。

如果有且仅有左儿子或有且仅有右儿子，把它仅有的儿子旋转上来——也就是把它反方向旋转下去，删除旋转后的它。当然，这个节点必须到这棵子树的叶子节点才会被删除。

如果既有左儿子又有右儿子，比较左右儿子优先级的大小，优先级大的旋转上来，——也就是把它反着优先级较大儿子的方向旋转下去，删除旋转后的它。当然，这个节点也必须到这棵子树的叶子节点才会被删除。

代码如下：

inline void deletei(int &x,int vali){

	if(!x)return ;

	int flag=vali==val[x]?-1:(vali<val[x]?0:1);

	if(flag!=-1)deletei(son[x][flag],vali);

	else{

		if(!son[x][0]&&!son[x][1]){

			--same[x];--sizei[x];

			if(same[x]==0)x=0;

		}else if(son[x][0]&&!son[x][1]){

			rotate(x,1);

			deletei(son[x][1],vali);

		}else if(!son[x][0]&&son[x][1]){

			rotate(x,0);

			deletei(son[x][0],vali);

		}else if(son[x][0]&&son[x][1]){

			flag=key[son[x][0]]>key[son[x][1]];

			rotate(x,flag);

			deletei(son[x][flag],vali);

		}

	}

	update(x);

}

记得更新~

3.4 根据关键码大小找排名 （默认排名为比它小的数的个数+1）score_rand

k ：被查找排名的关键码的值

如果找到空节点，返回；

如果 val[x]==k ，返回左儿子大小+1；

如果 val[x]>k ，往左儿子找；

反之往右儿子找。

代码如下：

inline int score_rank(int x,int k){

	if(!x)return 0;

	if(val[x]==k)return sizei[son[x][0]]+1;

	else if(val[x]>k)return score_rank(son[x][0],k);

	else if(val[x]<k)return score_rank(son[x][1],k)+sizei[son[x][0]]+same[x];

}

没有旋转，不用更新~

3.5 根据排名查找分数rank_score

k ：被查找分数的排名的值

如果找到空节点，返回；

如果左子树大小大于等于k，查找左子树；

如果左子树大小+与x相同的值的大小大于等于k，直接返回x的关键码的值；

否则查找右子树。

代码如下：

inline int rank_score(int x,int k){

	if(!x)return 0;

	if(sizei[son[x][0]]>=k)return rank_score(son[x][0],k);

	else if(sizei[son[x][0]]+same[x]>=k)return val[x];

	else return rank_score(son[x][1],k-sizei[son[x][0]]-same[x]);

}

3.6 查找前驱pre

前驱一定是被查找的关键码的值左边最大值。

k ：被查找的关键码的值

inf ：自定义的正无穷的值

如果查到空节点，返回会负无穷；

如果 val[x]>=k ，往左子树找；

否则返回x节点的关键码和往左子树查找结果的关键码的最大值。

代码如下：

inline int pre(int x,int k){

	if(!x)return -inf;

	if(val[x]>=k)return pre(son[x][0],k);

	else return max(val[x],pre(son[x][1],k));

}

3.7 查找后继suf

同查找前驱相反，只不过返回正无穷，而且是当 val[x]<=k 时往右子树找。

代码如下：

inline int suf(int x,int k){

	if(!x)return inf;

	if(val[x]<=k)return suf(son[x][1],k);

	else return min(val[x],suf(son[x][0],k));

}

模板

https://www.luogu.com.cn/problem/P3369

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cstdlib>

#include<ctime>

#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

const int N=1e5+10;

const int inf=0x3f3f3f3f;

int n,cnt,root,son[N][2],fa[N],val[N],key[N],sizei[N],same[N]; 

inline int read(){

	int s=0,w=1;

	char ch=getchar();

	while(ch<'0'||ch>'9'){

		if(ch=='-')w=-1;

		ch=getchar();

	}

	while(ch<='9'&&ch>='0'){

		s=s*10+ch-'0';

		ch=getchar();

	}

	return s*w;

}

inline void update(int x){

	sizei[x]=sizei[son[x][0]]+sizei[son[x][1]]+same[x];

}

inline void rotate(int &x,int flag){

	int y=son[x][flag^1];

	int change=son[y][flag];

	son[x][flag^1]=change;

	son[y][flag]=x;

	update(x);

	update(y);

	x=y;

}

inline void insert(int &x,int vali){

	if(!x){

		x=++cnt;

		sizei[x]=same[x]=1;

		val[x]=vali;

		key[x]=rand();

		return ;

	}

	if(val[x]==vali)return (void)(++sizei[x],++same[x]);

	int flag=vali>val[x];

	insert(son[x][flag],vali);

	if(key[x]<key[son[x][flag]])rotate(x,flag^1);

	update(x);

}

inline void deletei(int &x,int vali){

	if(!x)return ;

	int flag=vali==val[x]?-1:(vali<val[x]?0:1);

	if(flag!=-1)deletei(son[x][flag],vali);

	else{

		if(!son[x][0]&&!son[x][1]){

			--same[x];--sizei[x];

			if(same[x]==0)x=0;

		}else if(son[x][0]&&!son[x][1]){

			rotate(x,1);

			deletei(son[x][1],vali);

		}else if(!son[x][0]&&son[x][1]){

			rotate(x,0);

			deletei(son[x][0],vali);

		}else if(son[x][0]&&son[x][1]){

			flag=key[son[x][0]]>key[son[x][1]];

			rotate(x,flag);

			deletei(son[x][flag],vali);

		}

	}

	update(x);

}

inline int score_rank(int x,int k){

	if(!x)return 0;

	if(val[x]==k)return sizei[son[x][0]]+1;

	else if(val[x]>k)return score_rank(son[x][0],k);

	else if(val[x]<k)return score_rank(son[x][1],k)+sizei[son[x][0]]+same[x];

}

inline int rank_score(int x,int k){

	if(!x)return 0;

	if(sizei[son[x][0]]>=k)return rank_score(son[x][0],k);

	else if(sizei[son[x][0]]+same[x]>=k)return val[x];

	else return rank_score(son[x][1],k-sizei[son[x][0]]-same[x]);

}

inline int pre(int x,int k){

	if(!x)return -inf;

	if(val[x]>=k)return pre(son[x][0],k);

	else return max(val[x],pre(son[x][1],k));

}

inline int suf(int x,int k){

	if(!x)return inf;

	if(val[x]<=k)return suf(son[x][1],k);

	else return min(val[x],suf(son[x][0],k));

}

int main(){

	freopen("P3369.out","w",stdout);

	//IOS;

	//cin>>n;

	n=read();

	for(int i=1;i<=n;i++){

		int op,x;

		//cin>>op>>x;

		op=read();x=read();

		if(op==1)insert(root,x);

		else if(op==2)deletei(root,x);

		else if(op==3)cout<<score_rank(root,x)<<endl;

		else if(op==4)cout<<rank_score(root,x)<<endl;

		else if(op==5)cout<<pre(root,x)<<endl;

		else if(op==6)cout<<suf(root,x)<<endl;

	}

	return 0;

}

2021.12.06 平衡树——Treap的相关教程结束。

《2021.12.06 平衡树——Treap.doc》

下载本文的Word格式文档，以方便收藏与打印。

Copyright 2023. 昆居客 - IT编程,互联网信息技术文档大全!