关于splay的find函数
查看原帖
关于splay的find函数
556975
PNNNN楼主2024/4/1 21:35
inline void find(int P,int k){
	if(!k)return;
	if(P==val[k]){
		splay(k,0);
	}else{
		if(!son[k][P>val[k]])splay(k,0);
		else find(P,son[k][P>val[k]]);
	}return;
}

inline void find(int P,int k){
	if(!k)return;
	if(P==val[k]){
		splay(k,0);
	}else{
		find(P,son[k][P>val[k]]);
	}return;
}

下面的这份代码在平衡树模板TLE on #14,请问这是为什么? 这是我调用find函数的地方:

inline int pre(int P){
	find(P,rt);int x=rt;
	x=son[x][0];
	while(son[x][1])x=son[x][1];
	return x;
}

inline int nxt(int P){
	find(P,rt);int x=rt;
	x=son[x][1];
	while(son[x][0])x=son[x][0];
	return x;
}

且我在每次求x的前/后驱时,都插入了一个x

		}else if(opt==5){
			insert(x,rt,0);int res=pre(x);
			cout<<val[res]<<'\n';
			delet(x),splay(res,0);
		}else if(opt==6){
			insert(x,rt,0);int res=nxt(x);
			cout<<val[res]<<'\n';
			delet(x),splay(res,0);
		}
2024/4/1 21:35
加载中...