关于 Splay 的一个问题
  • 板块学术版
  • 楼主EricQian
  • 当前回复5
  • 已保存回复5
  • 发布时间2021/7/14 19:06
  • 上次更新2023/11/4 14:48:09
查看原帖
关于 Splay 的一个问题
113073
EricQian楼主2021/7/14 19:06

Splay\text{Splay}Delete\text{Delete} 操作中,我们已经将需要修改的节点旋转到了根节点,现在需要删去这个节点:(此时根节点有 两个儿子

如果按照如下方式删:

int Last=pre(),rt=root; 
ch[Last][1]=ch[rt][1];
fa[ch[rt][1]]=Last;
splay(Last);
clear(rt);

即先将右子树连到根节点的前驱上,再 Splay\text{Splay} 前驱 LastLast ,会发现会掉入死循环,可以见 测评记录

但是如果这样删:

int Last=pre(),rt=root; 
splay(Last);
ch[Last][1]=ch[rt][1];
fa[ch[rt][1]]=Last;
clear(rt);
pushup(Last);

即先 Splay\text{Splay} ,再连接右子树,就可以通过模板,测评记录

这是为什么呢?求各位巨佬解答

2021/7/14 19:06
加载中...