• 欢迎光临~

平衡树

开发技术 开发技术 2022-10-07 次浏览

功能:插入,删除,根据数值查排名,根据排名查数据,找前驱后继

您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作:

  1. 插入数值 x。

  2. 删除数值 x(若有多个相同的数,应只删除一个)。

  3. 查询数值 x 的排名(若有多个相同的数,应输出最小的排名)。

  4. 查询排名为 x 的数值。

  5. 求数值 x 的前驱(前驱定义为小于 x 的最大的数)。

  6. 求数值 x 的后继(后继定义为大于 x 的最小的数)。

注意: 数据保证查询的结果一定存在。


输入格式


第一行为 n,表示操作的个数。

接下来 n 行每行有两个数 opt 和 x,opt 表示操作的序号(1≤opt≤6)。


输出格式


对于操作 3,4,5,6 每行输出一个数,表示对应答案。


#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int INF=1e8;
int n,m;
int root,idx;
struct node
{
	int l,r;
	int cnt,size;
	int key,val;
}t[N];

void pushup(int p)
{
	t[p].size=t[t[p].l].size+t[t[p].r].size+t[p].cnt;
}
void zig(int &p)
{
	int q=t[p].l;
	t[p].l=t[q].r;
	t[q].r=p;p=q;
	pushup(t[p].r);
	pushup(p);
}
void zag(int &p)
{
	int q=t[p].r;
	t[p].r=t[q].l;
	t[q].l=p;p=q;
	pushup(t[p].l);
	pushup(p);
}
int get_node(int key)
{
	t[++idx].key=key;
	t[idx].val=rand();
	t[idx].size=t[idx].cnt=1;
	return idx;
}
void build()
{
	get_node(-INF);get_node(INF);
	root=1;
	t[1].r=2;
	if(t[1].val<t[2].val) zag(root);
	pushup(root);
}
void insert(int &p,int key)
{
	if(!p) p=get_node(key);
	else if(t[p].key==key) t[p].cnt++;
	else if(t[p].key>key)
	{
		insert(t[p].l,key);
		if(t[t[p].l].val>t[p].val) zig(p);
	}
	else
	{
		insert(t[p].r,key);
		if(t[t[p].r].val>t[p].val) zag(p);
	}
	pushup(p);
}
void remove(int &p,int key)
{
	if(!p) return;
	if(t[p].key==key)
	{
		if(t[p].cnt>1) t[p].cnt--;
		else if(t[p].l||t[p].r)
		{
			if(!t[p].r||t[t[p].l].val>t[t[p].r].val)
			{
				zig(p);
				remove(t[p].r,key);
			}
			else
			{
				zag(p);
				remove(t[p].l,key);
			}
		}
		else p=0;
	}
	else if(t[p].key>key) remove(t[p].l,key);
	else remove(t[p].r,key);
	pushup(p);
}
int get_key_by_rank(int p,int rank)
{
	if(!p) return 0;
	if(t[t[p].l].size>=rank) return get_key_by_rank(t[p].l,rank);
	if(t[t[p].l].size+t[p].cnt>=rank) return t[p].key;
	return get_key_by_rank(t[p].r,rank-t[t[p].l].size-t[p].cnt);
}
int get_rank_by_key(int p,int key)
{
	if(!p) return INF;
	if(t[p].key==key) return t[t[p].l].size+1;
	if(t[p].key>key) return get_rank_by_key(t[p].l,key);
	return t[t[p].l].size+t[p].cnt+get_rank_by_key(t[p].r,key);
}
int get_prev(int p,int key)
{
	if(!p) return -INF;
	if(t[p].key>=key) return get_prev(t[p].l,key);
	return max(t[p].key,get_prev(t[p].r,key));
}
int get_next(int p,int key)
{
	if(!p) return INF;
	if(t[p].key<=key) return get_next(t[p].r,key);
	return min(t[p].key,get_next(t[p].l,key));
}


int main(){
	
	build();
    scanf("%d", &n);
    while (n -- )
    {
        int opt, x;
        scanf("%d%d", &opt, &x);
        if (opt == 1) insert(root, x);
        else if (opt == 2) remove(root, x);
        else if (opt == 3) printf("%dn", get_rank_by_key(root, x) - 1);
        else if (opt == 4) printf("%dn", get_key_by_rank(root, x + 1));
        else if (opt == 5) printf("%dn", get_prev(root, x));
        else printf("%dn", get_next(root, x));
    }

	
	
	return 0;
}
程序员灯塔
转载请注明原文链接:平衡树
喜欢 (0)
违法和不良信息举报电话:022-22558618 举报邮箱:dljd@tidljd.com