关于平衡树

学术版

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

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

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

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

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

by 向北方 @ 2019-08-19 13:34:57

@noip

1.看内容，感觉说的挺好，也蛮有道理，提出了SBT算法。

2.在Winter Camp 2007中发表（我找到了）

by negiizhao @ 2019-08-19 13:34:58

@zmxqs 这个东西在他提出的时候确实没什么意义了，没找到有什么它能做而其他平衡树不能做的（别跟我说维护这东西），更没有什么优秀的性质，如果有什么用处的话早就投期刊了

by 向北方 @ 2019-08-19 13:35:56

@negiizhao 投了呀

by noip @ 2019-08-19 13:36:30

@zmxqs 看内容，感觉说的挺好，也蛮有道理，所以经过了权威认证！好有道理！

by noip @ 2019-08-19 13:36:41

@zmxqs 投在哪个期刊？

by noip @ 2019-08-19 13:36:52

Winter Camp 2007是个什么期刊

by 向北方 @ 2019-08-19 13:37:29

@noip 这我也不知道啊（大雾）网上看到的

by noip @ 2019-08-19 13:37:51

@zmxqs 结论：网上看到啥就是啥

by 向北方 @ 2019-08-19 13:38:18

Size Balanced Tree(SBT)是一种平衡二叉查找树。它的论文由中国广东中山纪念中学的陈启峰于2006年底完成，并在Winter Camp 2007中发表。由于SBT的拼写很容易找到中文谐音，它常被中国的OIer们戏称为“傻X树”、“Super BT”等。但它的性能并不SB，编写起来也并不BT。恰恰相反，SBT易于实现，且据陈启峰论文中所言，“这是目前为止速度最快的高级二叉搜索树”。它能在O(logn)的时间内完成所有BST的相关操作。而且由于SBT赖以保持平衡的是Size域而不是其他“无用”的域，它可以很方便地实现动态顺序统计中的select和rank。

这是 https://www.cnblogs.com/reflec94/archive/2011/01/22/1942095.html 里面的。

毕竟这么多个Oier其中那么多巨佬都认同SBT，我们就这么认为吧。像我这种蒟蒻能学会就不错了

by noip @ 2019-08-19 13:38:37

我之前网上看到啥就是啥然后被各路神仙怼死了（雾