萌新求助,关于平衡树(Splay)中erase操作的复杂度
  • 板块P3586 [POI2015] LOG
  • 楼主YeKai
  • 当前回复2
  • 已保存回复2
  • 发布时间2021/8/7 07:49
  • 上次更新2023/11/4 11:45:51
查看原帖
萌新求助,关于平衡树(Splay)中erase操作的复杂度
464922
YeKai楼主2021/8/7 07:49

我写了一个Splay,用权值代替每个数的存在次数。

在对任意结点删除任意数量时,先写了一个 erase(key,cnt) 形式的代码,结果最后一个点会T。

然后就尝试插入负数权的点,insert(key,-cnt),A了。

然后我又写了一个基于 insert 方式的 cut 函数,发现把 cut 函数最后两行(插入 00 权结点)注释掉后就会T。

那么这究竟是为什么?复杂度是假的吗?

2021/8/7 07:49
加载中...