P3369 【模板】普通平衡树 题解

难度:⭐⭐⭐⭐⭐
知识点:平衡树
题目链接

序言:调了超久的一道题!向提高组冲击的第一步!treap!

1. 入手程序

模板题么,就没什么思路了,既然是练习treap,直接开整呗~

2. 编程思路

首先,Treap=Tree+Heap,Tree指的是二叉排序树,Heap则是指堆
它融合了二叉排序树的优点:操作方便、多样
同时使用堆结构,和随机值规避了二叉排序树容易退化成一条链的问题
剩下的看代码吧~
放心,注释多到爆炸

3. AC代码

/*
size[i] 以i为根的子树的节点数
v[i] i节点的权值
num[i] 由于可能有重复(上文讲的是没有重复的),所以,我们将权值一样的存在一个节点里面,num数组存储的是i节点存的个数
son[i][2] 存储i节点的儿子,注意,这里不是完全二叉树所以需要存储儿子,son[i][0]表示左儿子,son[i][1]表示右儿子。
rd[i] i节点的一个随机值
*/
#include<bits/stdc++.h>
using namespace std;
const int MAX=100500;
int n;
int size[MAX],num[MAX],v[MAX],son[MAX][2],rd[MAX];
int x,opt,r,sum;//x,opt与题干中同义,sum为节点个数 
void gx(int g)//更新节点个数 
{
	size[g]=size[son[g][0]]+size[son[g][1]]+num[g];
	//g的节点数=左右儿子节点数之和+g本身存有数量
}
void xz(int &g,int d)//旋转,以g为根,d=0左旋,反之右旋 
{
	//x^1时,如果x为偶数则为x+1,否则为x-1
	//这里相当于1变0,0变1 
	int v1=son[g][d^1];//左旋时,v1为g的右儿子,反之为g的左儿子 
	son[g][d^1]=son[v1][d];
	//左旋时,g的右儿子变成v1的左儿子,反之g的左儿子变成v1的右儿子 
	son[v1][d]=g;
	//左旋时,v1的左儿子变成g,反之v1的右儿子变成g
	gx(g);
	gx(v1); 
	//更新父节点子节点个数 
	g=v1;//最后换根 
}
void cr(int &g,int x)//插入,以g为根,插入x 
{
	if(!g)//空树 
	{
		g=++sum;//节点总数加1 
		size[g]=num[g]=1;//于是有1个节点在树中了,当前节点有1个重复数字
		v[g]=x;//值为x
		rd[g]=rand();//生成随机值,拿来维护堆,防止退化成链
		return;
	}
	if(v[g]==x)//已有该权值,那么直接个数加加即可
	{
		num[g]++;
		size[g]++;
		return;
	}
	//继续向下寻找 
	int v1=(x>v[g]);//左儿子或右二子 
	cr(son[g][v1],x);
	if(rd[g]<rd[son[g][v1]])//这样转不破坏堆的性质
	{
		xz(g,v1^1);//旋转 
		//x^1时,如果x为偶数则为x+1,否则为x-1
		//这里相当于1变0,0变1 
	}
	gx(g);//更新父节点子节点个数 
}
void sc(int &g,int x)//根为g,删除x
{
	if(!g)//空节点,不可能有要删的这个点 
	{
		return;	
	}
	//如果x和v[g]不相等,直接转到相应子树解决问题	
	if(x<v[g])
	{
		sc(son[g][0],x);
	}
	else if(x>v[g])
	{
		sc(son[g][1],x);	
	}
	else//就在这棵树 
	{
		if(!son[g][0] && !son[g][1]) //木有在节点啦,x是叶子节点 
		{
			num[g]--;
			size[g]--;
			//扣掉个数 
			if(num[g]==0)//如果没数了,删除节点 
			{
				g=0;
			}
		}
		else if(son[g][0] && !son[g][1])
		{
			xz(g,1);//转~ 
			sc(son[g][1],x); 
		}
		else if(!son[g][0] && son[g][1])
		{
			xz(g,0);//转~ 
			sc(son[g][0],x); 
		}
		else if(son[g][0] && son[g][1])//俩都有,转大的 
		{
			int v1=(rd[son[g][0]]>rd[son[g][1]]);//按随机值排,完美避开强迫症~ 
			xz(g,v1);//转~ 
			sc(son[g][v1],x); 
		}
	}
	gx(g);
} 
int pm(int &g,int x)//根为g,查询x的排名 
{
	if(!g)//空空如也~
	{
		return 0;	
	}	
	if(v[g]==x)//返回左子树个数+1 
	{
		return size[son[g][0]]+1;
	}
	if(v[g]<x)//x在右子树,返回左子树个数+在右子树的排名 
	{
		return size[son[g][0]]+num[g]+pm(son[g][1],x); 
	}
	if(v[g]>x)//x在左子树,返回在左子树的排名 
	{
		return pm(son[g][0],x);
	}
} 
int cx(int &g,int x)
{
	if(g==0)//又是空空如也~
	{
		return 0;	
	} 
	if(size[son[g][0]]>=x)//左子树节点数>x,在左节点里找 
	{
		return cx(son[g][0],x); 
	}
	else if(size[son[g][0]]+num[g]<x)//左节点节点数<x,查右子树的第x-左子树节点个数-根储存个数 
	{
		return cx(son[g][1],x-num[g]-size[son[g][0]]);
	}
	else//当前就是要找的 
	{
		return v[g];
	}
}
int qq(int g,int x)//根为g,求x的前驱 
{
	if(g==0)//还是空空如也~ 
	{
		return -2000000005; 
	} 
	else if(v[g]>=x)//在根或右子树,去左子树找 
	{
		return qq(son[g][0],x);
	}
	else//在左子树,取根和右子树最大的那一个 
	{
		return max(v[g],qq(son[g][1],x)); 
	}
}
int hj(int g,int x)//根为g,求x的后继 
{
	if(g==0)//依旧空空如也~
	{
		return 2000000005;
	} 
	if(v[g]<=x)//在根或左子树,去右子树找 
	{
		return hj(son[g][1],x);
	}
	else//在左子树,取根或右子树最小的那一个 
	{
		return min(v[g],hj(son[g][0],x)); 
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>opt>>x;
		if(opt==1)//插入 x 数
		{
			cr(r,x);
		}
		else if(opt==2)//删除 x 数(若有多个相同的数,因只删除一个)
		{
			sc(r,x);
		}
		else if(opt==3)//查询 x 数的排名(排名定义为比当前数小的数的个数 +1 )
		{
			cout<<pm(r,x)<<endl;	
		} 
		else if(opt==4)//查询排名为 x 的数
		{
			cout<<cx(r,x)<<endl;
		}
		else if(opt==5)//求 x 的前驱(前驱定义为小于 x,且最大的数)
		{
			cout<<qq(r,x)<<endl;
		}
		else if(opt==6)//求 x 的后继(后继定义为大于 x,且最小的数)
		{
			cout<<hj(r,x)<<endl;
		}
	}
	return 0;
}

我是千文杜博,记住我呦~~

The end