在 Splay 的 Delete 操作中,我们已经将需要修改的节点旋转到了根节点,现在需要删去这个节点:(此时根节点有 两个儿子 )
如果按照如下方式删:
int Last=pre(),rt=root;
ch[Last][1]=ch[rt][1];
fa[ch[rt][1]]=Last;
splay(Last);
clear(rt);
即先将右子树连到根节点的前驱上,再 Splay 前驱 Last ,会发现会掉入死循环,可以见 测评记录
但是如果这样删:
int Last=pre(),rt=root;
splay(Last);
ch[Last][1]=ch[rt][1];
fa[ch[rt][1]]=Last;
clear(rt);
pushup(Last);
即先 Splay ,再连接右子树,就可以通过模板,测评记录
这是为什么呢?求各位巨佬解答