求大佬帮调一下蒟蒻的二叉搜索树!全部WA了
查看原帖
求大佬帮调一下蒟蒻的二叉搜索树!全部WA了
658726
qyz123123楼主2023/8/18 13:05

很奇怪啊,平衡树的二叉搜索树基础都是用的这个代码过的。怎么这个就过不了?

#include<cstdio>

const int INF = 2147483647;
const int N = 1e4+5;
int q, opt, x, cnt, root;
struct BST{
	int data, left, right, siz;
}t[N];

void up(int now)
{
	t[now].siz = t[t[now].left].siz+t[t[now].right].siz+1;
}

void insert(int &now, int data)
{
	if (now==0){
		now = ++cnt;
		t[now] = BST{data, 0, 0, 1};
		return ; 
	}
    ++t[now].siz;
    if (data>=t[now].data) insert(t[now].right, data);
    else insert(t[now].right, data);
    up(now);
}

int rank(int now, int data)//查询某一节点的排名
{
	if (!now) return 0;
	if (data>t[now].data) return t[t[now].left].siz+1+rank(t[now].right,data);
	return rank(t[now].left, data);
}
int find(int now, int rank)
{
	if (rank==t[t[now].left].siz+1) return t[now].data;
	else if (rank>t[t[now].left].siz+1) return find(t[now].right, rank-t[t[now].left].siz-1);
	else return find(t[now].left, rank);
}

int query_pre(int now, int data)
{
	if (now==0) return 0;
	if (data<=t[now].data) return query_pre(t[now].left, data);
	int tmp=query_pre(t[now].right, data);
	return tmp==0?t[now].data:tmp;
}

int query_suf(int now, int data)
{
	if (now==0) return 0;
	if (data>=t[now].data) return query_suf(t[now].right, data);
	int tmp=query_suf(t[now].left, data);
	return tmp==0?t[now].data:tmp;
}

inline int read()
{
	int x=0, f=1; char c=getchar();
	while (!(c>='0' && c<='9')){if (c=='-') f=-1; c=getchar();}
	while (c>='0' && c<='9'){x=(x<<3)+(x<<1)+c-48; c=getchar();}
	return f*x;
}

int main()
{
    q=read();
    while (q--){
    	opt=read(), x=read();
    	if (opt==1) printf("%d\n", rank(root, x)+1);
    	else if (opt==2) printf("%d\n", find(root, x));
    	else if (opt==3){
    		int ans=query_pre(root, x);
    		printf("%d\n", !ans?-INF:ans);
		}
		else if (opt==4){
			int ans=query_suf(root, x);
			printf("%d\n", !ans?INF:ans);
		}
		else insert(root, x);
	}
	return 0;
}
2023/8/18 13:05
加载中...