关于平衡树

学术版

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

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

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

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

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

by 向北方 @ 2019-08-18 20:09:07

@QwQ237

$A2:$ 出题人 **也不会毒瘤到卡你的$fhqTreap$算法，这东西常数其实并不大。（一般搜索树中，递归次数如果$\geq 1e6$就要当心反复调用函数的常数，但这东西在$\leq 1e5$的时候力量太小）** 所以说常数并不大，不用担心被卡。 $A3:$ 这里我连$Treap$也一起说了吧。红黑树：查找比$AVL$要差一些，但是插入和删除是比较快的，但又比$AVL$复杂，代码长，常数大，可能时间会打折扣。不过一般情况是忽略常数的。 $AVL$：查找效率高（因为过于平衡），插入删除较差，可能旋转多次。 $SBT$：和$AVL$其实差不多，是万能的，几乎可以取代$AVL$、红黑树。查找性能好（也是过于平衡导致），但插入删除和$AVL$一样甚至较慢，因为它还要维护整棵数的$size$. $Treap$：普通平衡树写法，是竞赛中最主流的树。（另一个是$Splay$) 这东西的优点在于：不用 **旋转** ，代码短，实现简单，好理解。而缺点在于：如果作为$LCT$的一棵 **可怜** 的辅助树，那么时间复杂度比$Splay$多一个$\log$，所以容易被卡。（随便卡卡就$TLE$了）大概就是这样，希望你能看懂。

by QwQ237 @ 2019-08-18 20:24:38

@zmxqs thx

by QwQ237 @ 2019-08-18 20:25:39

@zmxqs A4?

by QwQ237 @ 2019-08-18 20:28:34

@zmxqs 另外，

为啥论文里的统计数据表明SBT显著快于AVL？
fhqTreap的问题，其实是在某题解中看到“除了splay和fhqTreap都是高速平衡树”之后感觉有些疑惑。如果愿意的话，求给一下fhqTreap的效率大致介于哪两个平衡树之间？
再一次感谢您打那么多字

by 向北方 @ 2019-08-18 20:38:14

@QwQ237

补充A4：那lxl不喜欢写，这看个人习惯。我说dp难那dp就是假的了？不至于。

新：

$AVL$比$SBT$好的是，只是多加了几条语句，多了几次判断和旋转，用深度维护。而$SBT$的优势则在于，运行快，调试易，码量短，用途广（不小心写诗），用宽度进行维护。 **个人感觉这两个比较和$dfs$与$bfs$的比较差不多啊** $A2:$这要看你说的是插入删除，还是查找。 $A3:$不用谢。（大家都是$dalao$）

by 向北方 @ 2019-08-18 20:47:16

@QwQ237 算了，T2我都告诉你吧。

这里我把红黑树简写为RB（当然是Red and Blue）

对于插入而言：

删除同插入。查找： $AVL=SBT < AVL = RB

大概是这样。但是，由于 毒瘤出题人会出各种不同的数据卡你， 所以不是绝对的。这东西只是大部分而言。a < b表示a比b快。

by QwQ237 @ 2019-08-18 20:52:05

@zmxqs

“运行快”？都说比AVL慢许多啦。
另外问下fhqTreap的效率大致介于哪两个平衡树之间？或者说下它相比其他平衡树的优劣？
您比我巨多了

by QwQ237 @ 2019-08-18 20:53:16

%%%

by 向北方 @ 2019-08-18 20:59:30

@QwQ237

$A2$：$fhqTreap$比$Treap$的时间复杂度要优一点（很显然，这是因为**这东西不需要旋转**），相当于“无旋$Treap$”.基本时间复杂度是相等的。$fhqTreap$的插入删除，基本与$SBT$和$AVL$持平。查找吗……比$SBT$要优吧，但是和$AVL$、$RB$比还是略逊一筹啊。 **上面那个查找的比较错了，应该是：** $$Treap=SBT > AVL=RB$$

by QwQ237 @ 2019-08-18 21:08:18

@zmxqs 谢大佬

| 下一页