问一下splay模版的两个问题
  • 板块学术版
  • 楼主Jay朝花夕拾
  • 当前回复7
  • 已保存回复7
  • 发布时间2022/7/29 18:46
  • 上次更新2023/10/27 17:48:56
查看原帖
问一下splay模版的两个问题
479172
Jay朝花夕拾楼主2022/7/29 18:46

我参照了OI wiki的代码,但是有2个疑问 1.在查找一个数的排名时,假如输入了一个比当前平衡树中所有数都大的数,那么最后一次会停留在最大值的结点上,然后再次往右走来到空结的,此时是否需要将这个最大值结点执行一次splay操作呢?
2.查找一个数的前驱元素时,OI WIKI的代码是这样做的: \

  • 将这个数插入平衡树中
  • 由于splay操作,这个数一定在根结点,查找根结点左子树中最右的元素,得到答案
  • 将这个最右元素splay到根
  • 删除原先插入的数 我的疑问是,既然删除操作本质上也是先将这个数splay到根,那么,第三步将最右元素splay到根是否有必要?毕竟接下来又要将这个数splay到根...那还不如直接就删除合并呢

求大佬解惑...

2022/7/29 18:46
加载中...