关于Splay
  • 板块学术版
  • 楼主bsTiat
  • 当前回复11
  • 已保存回复11
  • 发布时间2022/3/19 17:59
  • 上次更新2023/10/28 06:11:28
查看原帖
关于Splay
211086
bsTiat楼主2022/3/19 17:59

菜鸡刚学平衡树,关于Splay有些疑问。 看了这份论文的摊还分析,能理解Splay的均摊复杂度是 O(logn)O(log n ) 的,但是我们可以很简单的构造数据使得Splay变成一条链,然后每次都对链尾进行操作,链尾又会被翻上来到链顶,还是一条链,这样复杂度不就变成 O(n)O( n ) 的了吗?

问题一:Splay是否可以被卡到单次操作 O(n)O( n )

问题二:平衡树推荐一共要学哪种,在OI赛场上使用的?

问题三:各OI主流平衡树的常数大小比较是怎样的?哪些比较优,哪些比较劣?

问题四:是否每种平衡树都有专属的个性操作无法代替,是否应学习多种平衡树甚至全部?

2022/3/19 17:59
加载中...