@[QwQ237](/space/show?uid=217119)
$A1:$ 所有方面是不存在的。平衡树的算法还是以$LCT$和$Splay$为主，那个$fhqTreap$并不能完全替代之。
$A2:$ 出题人 **也不会毒瘤到卡你的$fhqTreap$算法，这东西常数其实并不大。（一般搜索树中，递归次数如果$\geq 1e6$就要当心反复调用函数的常数，但这东西在$\leq 1e5$的时候力量太小）** 所以说常数并不大，不用担心被卡。
$A3:$ 这里我连$Treap$也一起说了吧。
红黑树：查找比$AVL$要差一些，但是插入和删除是比较快的，但又比$AVL$复杂，代码长，常数大，可能时间会打折扣。不过一般情况是忽略常数的。
$AVL$：查找效率高（因为过于平衡），插入删除较差，可能旋转多次。
$SBT$：和$AVL$其实差不多，是万能的，几乎可以取代$AVL$、红黑树。查找性能好（也是过于平衡导致），但插入删除和$AVL$一样甚至较慢，因为它还要维护整棵数的$size$.
$Treap$：普通平衡树写法，是竞赛中最主流的树。（另一个是$Splay$) 这东西的优点在于：不用 **旋转** ，代码短，实现简单，好理解。 而缺点在于：如果作为$LCT$的一棵 **可怜** 的辅助树，那么时间复杂度比$Splay$多一个$\log$，所以容易被卡。（随便卡卡就$TLE$了）
大概就是这样，希望你能看懂。
by 向北方 @ 2019-08-18 20:09:07
@[zmxqs](/space/show?uid=139960) thx
by QwQ237 @ 2019-08-18 20:24:38
@[zmxqs](/space/show?uid=139960) A4?
by QwQ237 @ 2019-08-18 20:25:39
@[zmxqs](/space/show?uid=139960) 另外，
- 为啥论文里的统计数据表明SBT显著快于AVL？
- fhqTreap的问题，其实是在某题解中看到“除了splay和fhqTreap都是高速平衡树”之后感觉有些疑惑。如果愿意的话，求给一下fhqTreap的效率大致介于哪两个平衡树之间？
- **再一次感谢您打那么多字**
by QwQ237 @ 2019-08-18 20:28:34
@[QwQ237](/space/show?uid=217119)
补充$A4$：那$lxl$不喜欢写，这看个人习惯。我说$dp$难那$dp$就是假的了？不至于。
新：
$A1$:这是有争议的。
$AVL$比$SBT$好的是，只是多加了几条语句，多了几次判断和旋转，用深度维护。
而$SBT$的优势则在于，运行快， 调试易， 码量短，用途广（不小心写诗），用宽度进行维护。
**个人感觉这两个比较和$dfs$与$bfs$的比较差不多啊**
$A2:$这要看你说的是插入删除，还是查找。
$A3:$不用谢。（大家都是$dalao$）
by 向北方 @ 2019-08-18 20:38:14
@[QwQ237](/space/show?uid=217119) 算了，$T2$我都告诉你吧。
这里我把红黑树简写为$RB$（当然是$Red$ $and$ $Blue$）
对于插入而言：
$Treap<AVL<SBT$，其中$RB$不一定。
删除同插入。
查找：
$AVL=SBT < AVL = RB$
大概是这样。但是，由于 **毒瘤出题人会出各种不同的数据卡你，** 所以不是绝对的。这东西只是大部分而言。$a < b$表示$a$比$b$快。
by 向北方 @ 2019-08-18 20:47:16
@[zmxqs](/space/show?uid=139960)
- “运行快”？都说比AVL慢许多啦。
- 另外问下fhqTreap的效率大致介于哪两个平衡树之间？或者说下它相比其他平衡树的优劣？
- 您比我巨多了
by QwQ237 @ 2019-08-18 20:52:05
%%%
by QwQ237 @ 2019-08-18 20:53:16
@[QwQ237](/space/show?uid=217119)
$A1$:不信你去$baidu$看看，还是各有千秋。如果慢多了，那要$SBT$这东西干么？
$A2$：$fhqTreap$比$Treap$的时间复杂度要优一点（很显然，这是因为**这东西不需要旋转**），相当于“无旋$Treap$”.基本时间复杂度是相等的。$fhqTreap$的插入删除，基本与$SBT$和$AVL$持平。查找吗……比$SBT$要优吧，但是和$AVL$、$RB$比还是略逊一筹啊。
**上面那个查找的比较错了，应该是：**
$$Treap=SBT > AVL=RB$$
by 向北方 @ 2019-08-18 20:59:30
@[zmxqs](/space/show?uid=139960) 谢大佬
by QwQ237 @ 2019-08-18 21:08:18