RT
void ins(int x){//插入
if(!rt){//原来是一个空树
val[++tot]=x;
rt=tot;
cnt[tot]++;
update(rt);
return;//插入,不用Splay(一个点你Splay个寂寞
}
int cnr=rt,f=0;
while(1){
if(x==val[cnr]){//原来集合中已经包含
cnt[cnr]++;//增加节点出现个数
// update(cnr);//更新(升级 该节点
// update(f);//更新(升级 父亲节点
splay(cnr);//旋转的时候更新了
return;
}
f=cnr;
cnr=ch[cnr][val[cnr]<x];//一步写好
if(!cnr){
val[++tot]=x;
cnt[tot]++;
fa[tot]=f;
ch[f][val[f]<x]=tot;
// update(tot);
// update(f);
splay(tot);//旋转的时候都更新了
return;
}
}
}
写注释的时候发现的,手摸了一遍,反正都要旋转上去的,旋转的时候也会更新?,好奇怪