关于平衡树

学术版

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

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

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

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

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

by 向北方 @ 2019-08-19 13:42:46

@142857cs SPFA是一种数据结构没毛病。别扯，我们说的是SBT

by QwQ237 @ 2019-08-19 13:42:57

@zmxqs ？？？咋吵起来了

by 向北方 @ 2019-08-19 13:43:04

@noip 不止我说啊，那么多巨佬、神仙、Oier、Acmer

by noip @ 2019-08-19 13:43:13

你说这个"SBT"可以取代"Red and Blue Tree"，那就可以

by 向北方 @ 2019-08-19 13:44:06

@noip 这东西总有它的优点和缺点。

我们怎么又说到红黑树了

by noip @ 2019-08-19 13:44:53

@zmxqs 原来红黑树叫"Red and Blue Tree"

by 向北方 @ 2019-08-19 13:45:02

@QwQ237 感觉我打不过noip

by 向北方 @ 2019-08-19 13:45:36

@noip 我一时即兴的翻译。这东西是我为了方便说才这么说的。

by negiizhao @ 2019-08-19 13:45:39

@zmxqs 我们说的论文是指发表在权威期刊或者会议上的paper，至少也是个thesis，当然有时候一些同行评审过的厉害的文章没投的话也可以，这种最多是个类essay的文章是不算的。当然不是说这东西不对，重点是这东西确实没有应用或理论的价值，所谓速度最快的测试也是不对的，用size平衡的在几十年前也有wbt了。

by 向北方 @ 2019-08-19 13:46:02

@noip 好像blue是蓝色