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;
}