data-structures - 什么时候陷阱有用？

Question

在什么样的情况下使用最优化的数据结构？我一直在寻找这方面的答案，但还没有真正找到任何具体的东西。

还有另一个stackoverflow问题询问何时使用treap，但没有给出真实世界的例子。

最常见的优势似乎是它们比例如红黑树更容易实现，但几乎每个人都使用预先编写的实现，所以它似乎并不相关。

Answer 1

它是在随机算法类中用作示例的最佳数据结构。

好吧，抛开轻率不谈，Aragon 和 Seidel 提出的狭隘优势包括以下几点。

• 它们很简单。是的，你的标准库可能有一个可用的红黑树，但它可能没有提供足够的钩子来完成一些可以用二叉搜索树完成的有趣的事情（例如，顺序统计）。拆分和合并也简单得多。

• 假设优先级是通过对键进行散列计算的，它们使用的空间比红黑树略少。在实践中，如果红黑树可以窃取颜色的指针位，这并不重要。

• 它们可能比红黑树更快。无论如何，我都没有寻找证据。

最大的缺点是性能保证仅在预期中。人们从哈希表中学到了很难的方法，即通过分析随机算法假设的健忘对手在现实世界中通常不会那么健忘。

我认为可以公平地说，trap 是一个有趣的想法，但结果却没有产生很多实际影响。是研究。那个会发生。

Answer 2

Treaps 的一个非常不寻常的特性是它们对插入/删除的顺序不敏感。

由于插入/删除是基于随机优先级进行的，如果将 $n$ 个元素添加到空的treap，无论插入发生的顺序如何，treap 看起来都完全相同。

因此，对手无法查看treap 并找出插入元素的顺序。