WBLT

[Ir1d]

https://oi-wiki.org/ds/wblt/

OI Wiki 是一个编程竞赛知识整合站点，提供有趣又实用的编程竞赛知识以及其他有帮助的内容，帮助广大编程竞赛爱好者更快更深入地学习编程竞赛竞赛

[Cat-shao]

ratio为什么是5？
这种WBT有相关论文吗？我想看看

[nik-nul]

文中取值条件应该是有问题的.
这篇文章严格讨论了原始的 WBT 的常数取值的问题:
https://yoichihirai.com/bst.pdf

[AtomAlpaca]

文中取值条件是按照原始论文 https://dl.acm.org/doi/pdf/10.1145/800152.804906 的单个参数 $\alpha$ 控制旋转的, 您给出的文献是用两个参数 $\Delta, \Gamma$ 分别控制单旋和双旋的, 是文中方法的一种拓展
其实您会发现文中根据 $\alpha$ 算出的双旋参数恰好是 $\Gamma$ 的下界

[nik-nul]

是的, 现在文中的条件是正确的.
本评论作者发表评论之时看的应该是 这个版本 的 WBLT, 上面的是非常经典的 ratio=5 的错误实现. 一些很著名的语言, 比如 MIT-Scheme 曾经用的就是此错误版本 (http://git.savannah.gnu.org/cgit/mit-scheme.git/commit/?id=fa7ec497241664b891e2b57c8330b47e6c8ede11).
虽然现在文档中的实现是正确的，但是正文中直接嵌入的和 code/wblt/wblt_2.cpp 中写的实现利用了浮点数, 恐怕具有一定的性能问题.
现在采用 WBLT 作为 set 和 map 的具体实现的语言一般采用的都是两个参数的新方法, 比如 Haskell (https://github.com/haskell/containers/blob/master/containers/src/Data/Set/Internal.hs#L1813). 此种方法相较于论文中的方法性能应该会更好, 而且就个人而言也便于记忆. 即使正确性的证明或许会比较难以理解, 但是总体上来看可能是更合适于写在 wiki 中的.

[Cat-shao]

（好像WBT的一些变种 ratio取值有问题

[CodingJellyfish]

ratio取值非常有问题。基本上这种写法是假的。

[nuo0930]

您好请问能具体指一下哪里有问题吗

[AtomAlpaca]

应该是指之前的版本有问题

[NFLSCode]

leafy并不是结点多的意思罢

[by-legend]

求助一下大家,我ratio取值最早学的是4,这里写的是二,但我在加强版和普通版里面ratio取值的速度 从快到慢 为 :2 3 4 1,这是咋回事啊?

[by-legend]

搞错了,这里写的是3