为什么平衡树常数大？

学术版

ppip @ 2023-02-16 20:59:56

主要是因为高度不是线段树那样足够稳定的还是平衡操作常数大

如果一些平衡树的常数大原因不同也可以说一说

最后为什么 旋转 treap 跑得最快

by ppip @ 2023-02-16 21:02:00

补充一个问题，结构体好还是一堆数组好

by dehsirehC @ 2023-02-16 21:02:40

比如说你考虑 fhq treap 一次操作就要 split 和 merge 好几次，所以常数当然大

by dehsirehC @ 2023-02-16 21:02:57

结构体寻址更快吧，应该感觉结构体更快

by QAQ__ @ 2023-02-16 21:04:29

结构体和一堆数组的唯一差别不是内存是否连续吗？

by reveal @ 2023-02-16 21:04:47

  1. both，一些平衡树高度容易达到 2\log n，并且平衡常数大（当然还有 Splay 本身势能分析里的 6 倍常数，无旋 Treap 每次操作两遍等）。
  2. 说明你没有写出工业级的红黑树。
  3. 一般是结构体，寻址较为友好。

by ppip @ 2023-02-16 21:08:43

感谢。

by QwQcOrZ @ 2023-02-16 21:10:41

感觉各有各的原因...

比如 splay 的话你旋一次要进行的操作一堆，寻址还不连续。

fhq 主要因为每次要裂出来再合并回去，这部分自带一个若干倍常数。

旋转 treap 跑得最快 这你哪听说的。每种平衡树在不同的操作下展现出来的常数都是不同的，只能说各有千秋。

by QwQcOrZ @ 2023-02-16 21:12:26

@liqingyang 亲测结构体如果里开的东西很多的话非常慢 T^T，寻址会直接裂开。

by QwQcOrZ @ 2023-02-16 21:14:35

@ppip 如果结构体里只有 \mathcal O(1) 的信息的话应该差别不大。

如果达到 \mathcal O(\sqrt n) 这种级别，有常数需求的话千万别开。

by QAQ__ @ 2023-02-16 21:19:10

@reveal 能具体讲一下结构体为啥快吗谢谢

| 下一页