为什么我写的splay树是从大到小排列
查看原帖
为什么我写的splay树是从大到小排列
1393299
jiangdr楼主2024/9/2 14:37
#include<bits/stdc++.h>
using namespace std;
struct edge
{
	int ch[2],val,size,cnt,fa;
}tree[10020];
int zong=0,root;
void updata(int x)
{
	tree[x].size=tree[x].cnt+tree[tree[x].ch[0]].size+tree[tree[x].ch[1]].size;
}
void rorate(int x)
{
//                Y                   X
//               / \                 / \
//              X   C   ----->      A   Y
//             / \                     / \
//			  A   B                   B   C
	int father=tree[x].fa;
	int g_father=tree[father].fa;
	int ki=tree[father].ch[1]==x;
	tree[father].ch[ki]=tree[x].ch[ki^1];//B为Y的左儿子 
	tree[tree[x].ch[ki^1]].fa=father;//B的父亲是Y
	tree[father].fa=x;//Y的父亲是X
	tree[x].ch[ki^1]=father;//X的右儿子是Y
	tree[x].fa=g_father;//X的父亲是祖父
	tree[g_father].ch[tree[g_father].ch[1]==father]=x;//祖父的儿子是X
	updata(father);
	updata(x);//注意顺序 
}
void splay(int x,int goal)//将X移动到goal的儿子 
{
	while(tree[x].fa!=goal)//直到旋成儿子
	{
		int father=tree[x].fa;
	    int g_father=tree[father].fa;
	    if(g_father!=goal)//如果goal的儿子是X,那么进行单旋,否则进行双旋 
	    {
	    	(tree[father].ch[1]==x)^(tree[g_father].ch[1]==father)?rorate(x):rorate(father);
		}
		rorate(x);
	}
	if(goal==0) root=x;//每次splay后goal是0时都要更新根节点 
}
void insert(int x)//插入函数 
{
	int now=root,father=0;//父亲要不断更新,在创建新点时要用到 
	while(now&&tree[now].val!=x)//有值且不是要找的点时往下进行 
	{
		father=now;
		now=tree[now].ch[now>tree[now].val];
	}
	if(now) tree[now].cnt++;//重复加权 
	else//创建新点 
	{
		zong++,now=zong;
		tree[zong].val=x;
		if(father) tree[father].ch[now>tree[father].val]=now;
		//有父亲就更新儿子,没有则树是空的,splay后成为根 
		tree[zong].fa=father;
		tree[zong].cnt=tree[zong].size=1;
	}
	splay(now,0);//转回根 
}
void find(int x)//查询X本身或较近点并转到根 
{
	int now=root;
	if(!now) return;//树是空的
	while(tree[now].ch[tree[now].val<x]&&tree[now].val!=x)
	{
		//上述更新条件为有符合大小关系的儿子且值还没找到
		now=tree[now].ch[tree[now].val<x];
	}
	splay(now,0);
}
int find_jiedian(int x)//已知排名找相应节点,
{
	int now=root;
	
	while(1)
	{
		if(tree[tree[now].ch[0]].size>=x) now=tree[now].ch[0];
		else
		{
			x-=(tree[tree[now].ch[0]].size+tree[now].cnt);
			if(x<=0) return now;
			else now=tree[now].ch[1];
		}
	}
}
int find_paiming(int x)//已知节点找排名,val值越小越靠前 
{
	splay(x,0);
	return tree[tree[x].ch[0]].size+1;
}
int pre(int x)//找前驱,小于X的最大值 
{
	find(x);
	int now=root;
	now=tree[now].ch[0];
	while(tree[now].ch[1])
	{
		now=tree[now].ch[1];
	} 
	return now;
}
int net(int x)//找后继,大于X的最小值 
{
	find(x);
	int now=root;
	now=tree[now].ch[1];
	while(tree[now].ch[0])
	{
		now=tree[now].ch[0];
	} 
	return now;
}
void del(int x)//删除某点
{
	int pre_x=pre(x);
	int net_x=net(x);
	splay(pre_x,0);
	splay(net_x,pre_x);
	//比前驱大,比后继小
	//构建以前驱为根,且其右儿子为后继,则后继的左儿子是该点 
	if(tree[tree[net_x].ch[0]].cnt>1)//此时该点cnt值大于1 
	{
		
		tree[tree[net_x].ch[0]].cnt--;
		splay(tree[net_x].ch[0],0);
	}
	else//此时该点值为1,删除时注意更新size值 
	{
		tree[net_x].ch[0]=0;
		tree[net_x].size--;
		tree[pre_x].size--;
	}
} 
int main()
{
	for(int i=1;i<=10;i++)
	{
		int x;
		cin>>x;
		insert(x);
	}
	int m;
	cin>>m;
	cout<<find_jiedian(m+1);
	return 0;
}
2024/9/2 14:37
加载中...