关于平衡树

回复帖子

@QwQ237 2019-08-18 19:44 回复
  1. 除了LCT外,有哪些平衡树可以在所有方面完全取代splay(听说有fhqTreap)?
  2. fhqTreap的常数如何?
  3. SBT、AVL、红黑树三种平衡树哪一个最快(如果都差不多,可以大致讲一下各自的优缺点)?
  4. 为什么lxl认为SBT是假的?

求大佬解答任何一条,感激不尽!

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

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

@zmxqs 2019-08-18 20:09 回复 举报

@QwQ237

$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$了)

大概就是这样,希望你能看懂。

@QwQ237 2019-08-18 20:28 回复 举报

@zmxqs 另外,

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

@QwQ237

补充$A4$:那$lxl$不喜欢写,这看个人习惯。我说$dp$难那$dp$就是假的了?不至于。

新:

$A1$:这是有争议的。

$AVL$比$SBT$好的是,只是多加了几条语句,多了几次判断和旋转,用深度维护。

而$SBT$的优势则在于,运行快, 调试易, 码量短,用途广(不小心写诗),用宽度进行维护。

个人感觉这两个比较和$dfs$与$bfs$的比较差不多啊

$A2:$这要看你说的是插入删除,还是查找。

$A3:$不用谢。(大家都是$dalao$)

@zmxqs 2019-08-18 20:47 回复 举报

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

这里我把红黑树简写为$RB$(当然是$Red$ $and$ $Blue$)

对于插入而言:

$Treap<AVL<SBT$,其中$RB$不一定。

删除同插入。

查找:

$AVL=SBT < AVL = RB$

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

@QwQ237 2019-08-18 20:52 回复 举报

@zmxqs

  • “运行快”?都说比AVL慢许多啦。
  • 另外问下fhqTreap的效率大致介于哪两个平衡树之间?或者说下它相比其他平衡树的优劣?
  • 您比我巨多了
@zmxqs 2019-08-18 20:59 回复 举报

@QwQ237

$A1$:不信你去$baidu$看看,还是各有千秋。如果慢多了,那要$SBT$这东西干么?

$A2$:$fhqTreap$比$Treap$的时间复杂度要优一点(很显然,这是因为这东西不需要旋转),相当于“无旋$Treap$”.基本时间复杂度是相等的。$fhqTreap$的插入删除,基本与$SBT$和$AVL$持平。查找吗……比$SBT$要优吧,但是和$AVL$、$RB$比还是略逊一筹啊。

上面那个查找的比较错了,应该是:

$$Treap=SBT > AVL=RB$$

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。