【求助】关于Splay的一个优化
  • 板块学术版
  • 楼主2020kanade
  • 当前回复4
  • 已保存回复4
  • 发布时间2022/7/7 23:16
  • 上次更新2023/10/27 21:32:31
查看原帖
【求助】关于Splay的一个优化
456724
2020kanade楼主2022/7/7 23:16

众所周知Splay因为复杂度含有均摊单次单log的伸展操作导致常数巨大。

之前听说了某种优化:

貌似是当当前结点右子树的大小超过整棵树还是当前结点子树的一半的时候,直接旋转右子树到根,可以把伸展的均摊复杂度降到常数水平。

请问这种东西是否正确,以及严格证明,感性写了几个柿子感觉好像没错......

2022/7/7 23:16
加载中...