问
  • 板块学术版
  • 楼主Autream
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/6/3 20:16
  • 上次更新2024/6/3 22:01:12
查看原帖
问
941431
Autream楼主2024/6/3 20:16

Splay 中查询前驱后缀和删除的代码有以下两种版本,哪一种更好(适用范围更广)?

1:

int query_pre() {
  int k=ch[rt][0];
  if(!k) {
    return k;
  }
  while(ch[k][1]) k=ch[k][1];
  splay(k);//splay(5/7)
  return k;
}
int query_suc() {
  int k=ch[rt][1];
  if(!k) {
    return k;
  }
  while(ch[k][0]) k=ch[k][0];
  splay(k);//splay(6/7)
  return k;
}
void remove(int x) {
  int k=rt;
  while(x!=val[k]) {
    k=ch[k][x>val[k]];
  }
  splay(k);//splay(7/7)
  if(cnt[rt]>1) {
    cnt[rt]--;
    maintain(rt);
    return ;
  }
  if(!ch[rt][0]&&!ch[rt][1]) {
    del(rt);
    rt=0;
    return ;
  }
  if(!ch[rt][0]) {
    k=rt,rt=ch[rt][1],fa[rt]=0;
    del(k);
    return ;
  }
  if(!ch[rt][1]) {
    k=rt,rt=ch[rt][0],fa[rt]=0;
    del(k);
    return ;
  }
  k=rt;
  int t=query_pre();
  ch[t][1]=ch[k][1];
  fa[ch[k][1]]=t;
  del(k);
  maintain(rt);
}

2 :

int pre(int x){
	find(x);
	if(x>val[rt]) return rt;
	ll cur=son[rt][0];
	while(son[cur][1]) cur=son[cur][1];
	return cur;
}

int succ(int x){
	find(x);
	if(x<val[rt]) return rt;
	int cur=son[rt][1];
	while(son[cur][0]) cur=son[cur][0];
	return cur;
}

void remove(int x){
	int last=pre(x),nxt=succ(x);
	splay(last);splay(nxt,last);
	int del=son[nxt][0];
	if(cnt[del]>1){
		cnt[del]--;
		splay(del);
	}
	else son[nxt][0]=0;
}
2024/6/3 20:16
加载中...