scala - “布罗德搜索树”真的实现了实用吗？

Question

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

• Haskellcontainers使用亚当斯树；
• OCaml 标准库使用 AVL 树；
• Scala 的不可变排序映射是使用红黑树实现的。

如果 Brodal 树真的有这么好的效果，为什么没有被改编成主流的函数式编程语言标准库呢？事实上，我根本没有见过 Brodal 树的一种实现！

具体来说，这是因为：

• 它们很难（或实际上几乎不可能）正确实施；
• 常数很大，实际收益似乎很小；
• 其他原因；
• 还是上述的组合？

标签： scalahaskelldata-structuresfunctional-programmingocaml

Answer 1

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

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

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

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