菜鸡刚学平衡树,关于Splay有些疑问。
看了这份论文的摊还分析,能理解Splay的均摊复杂度是 O(logn) 的,但是我们可以很简单的构造数据使得Splay变成一条链,然后每次都对链尾进行操作,链尾又会被翻上来到链顶,还是一条链,这样复杂度不就变成 O(n) 的了吗?
问题一:Splay是否可以被卡到单次操作 O(n) ?
问题二:平衡树推荐一共要学哪种,在OI赛场上使用的?
问题三:各OI主流平衡树的常数大小比较是怎样的?哪些比较优,哪些比较劣?
问题四:是否每种平衡树都有专属的个性操作无法代替,是否应学习多种平衡树甚至全部?