关于平衡树

学术版

QwQ237 @ 2019-08-18 19:44:50

  1. 除了LCT外，有哪些平衡树可以在所有方面完全取代splay（听说有fhqTreap）？
  2. fhqTreap的常数如何？
  3. SBT、AVL、红黑树三种平衡树哪一个最快（如果都差不多，可以大致讲一下各自的优缺点）？
  4. 为什么lxl认为SBT是假的？

求大佬解答任何一条，感激不尽！

百度尚不能给出客观结果。

管理提示：请各位不要进行任何的语言攻击，若发现将会被处以禁言。

by noip @ 2019-08-18 23:08:40

@zmxqs 能取代红黑树和AVL才有鬼了

by noip @ 2019-08-18 23:08:58

要是比红黑树好那咋没见啥人用呢

by noip @ 2019-08-18 23:09:20

因为所谓的"SBT"严格不优于BB[1/3}Tree

by noip @ 2019-08-18 23:09:27

所以我觉得是假的

by noip @ 2019-08-18 23:12:54

你找找论文看看"SBT"学术界承不承认有这么个东西...

by QwQ237 @ 2019-08-19 12:38:06

惊现lxl！

by QwQ237 @ 2019-08-19 12:39:32

@zmxqs 所以关于sbt，它咋样？

还烦请您给一下（如果有的话）您回答的依据（链接），我再看看。

by 向北方 @ 2019-08-19 12:42:17

@QwQ237 SBT……没想到我被lxl吊打了，而且是摁在地板上敲……

个人认为，关于SBT你可以左转一个学步园的博客区，其中对BST与SBT的联系、区别作了详细阐述。

by 向北方 @ 2019-08-19 12:44:26

我回答的依据？——

1.个人经验（qaq）

2.网上博文（比如上述）

3.题解（逃）

by 向北方 @ 2019-08-19 12:53:27

@noip 有SBT这个东西啊。原因：

  1. 洛谷数据结构里搜的到SBT这东西

  2. 百度也搜的到SBT这东西

  3. SBT本来就是一种数据结构好不好

对于之前的，它确实严格不优于那个什么Tree，但是 毕竟人家辛辛苦苦创造了这个数据结构（或者说算法）也不容易，也是广为人知的东西，怎么能像SPFA一样把它打死，并摁倒在地板。 （大雾逃）

上一页 | 下一页