关于平衡树

学术版

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

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

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

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

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


by 向北方 @ 2019-08-19 15:21:00

@ouuan 那个第3句话好像我说过,我没翻到是哪一页,劳烦帮我找找?因为这东西有语境


by 向北方 @ 2019-08-19 15:21:50

@ouuan 我只会Markdown 别喷我 我用的是Markdown


by 向北方 @ 2019-08-19 15:22:23

@[Juan_feng](/space/show?uid=66965) 我没有装睡,这是认真的

by ouuan @ 2019-08-19 15:22:45

您还需要我解释上面您的 10 条回复除了“这里是错了没问题”外为什么无法反驳我列举的那些错误吗...


by 向北方 @ 2019-08-19 15:23:54

第2条我没错啊


by 向北方 @ 2019-08-19 15:24:23

递归次数少正说明了常数少

而且不可能存在1e7的题,因为这东西n \log n卡不过去的


by 向北方 @ 2019-08-19 15:24:35

那只是一个顺便的说法


by 向北方 @ 2019-08-19 15:24:50

@ouuan 我们一个个来说


by 向北方 @ 2019-08-19 15:25:12

第一条我错了,没问题。第二条就有所商榷


by 向北方 @ 2019-08-19 15:26:53

我在第2条中明确说了:

“但这东西在\leq 1e5的时候力量太小” ,而“这东西”指的就是常数,前一个半句也明确说明了。这显然论证出了常数小。


上一页 | 下一页