"Brodal搜索树"真的已经实用了吗？

Question

Brodal等.在他们的ESA '06论文中证明了存在一个纯函数结构,具有对数时间搜索,更新和插入以及恒定时间合并.(注意我不是在谈论Brodal堆,它是一种不同的数据结构,广泛用于实现纯粹的功能优先级队列.)这似乎是一个非常有利可图的结果,应该导致高效的纯功能集和映射,但我没有看到他们在任何地方使用过:

• Haskell containers使用亚当斯树;
• OCaml标准库使用AVL树;
• Scala的不可变排序映射使用红黑树实现.

如果Brodal树真的有这么好的结果,为什么它们没有被改编成主流的函数式编程语言标准库？事实上,我根本没有看到一个Brodal树的实现!

具体来说,这是因为:

• 它们非常难(或实际上几乎不可能)正确实施;
• 常数非常大,实际收益似乎很小;
• 其他原因;
• 或上述的组合？

Answer 1

正如评论中提到的，论文中的信息非常有限，导致人们怀疑非常大的常数，此外：

1. 该结构实际​​上并未声称支持 O(1) 时间内的一般合并。它仅声称支持更受限制的连接函数，连接相对于彼此排序的树。给定一种分割树的方法，此操作对于并行计算很有用，但在这种情况下，对数连接对于任何实际目的来说都相当便宜。
2. 该结构不支持元素拆分，并且没有为并集、交集等提供有效的实现。

与上面的内容有些重叠，阅读这篇文章，我认为结论中的以下注释可能是为什么没有为实施做出太多努力的原因

拆分将使每个树集合的此属性无效，并将导致 (log n log log n) 搜索和更新时间。