Jus*_*guy 5 treap data-structures
在什么样的情况下，treap 是使用的最佳数据结构？我一直在寻找这方面的答案，但还没有真正找到任何具体的东西。
还有另一个stackoverflow问题询问何时使用 treap 但那里没有给出真实世界的例子。
最常见的优点似乎是它们比例如红黑树更容易实现，但几乎每个人都使用预先编写的实现，所以它似乎并不相关。
它是在随机算法类中用作示例的最佳数据结构。
好吧，撇开轻率不谈，阿拉贡和塞德尔提出的狭隘优势包括以下几点。
它们很简单。是的，您的标准库可能有可用的红黑树，但它很可能没有提供足够的钩子来完成一些可以使用二叉搜索树完成的有趣的事情（例如，顺序统计）。拆分和合并也简单得多。
假设优先级是通过散列键来计算的，它们使用的空间比红黑树略少。实际上，如果红黑树可以窃取颜色的指针位，这并不重要。
它们可能比红黑树更快。我还没有寻找任何证据。
最大的缺点是性能保证仅在预期中。人们通过哈希表惨痛地认识到，通过随机算法分析假设的不经意的对手在现实世界中通常并不那么不经意。
我认为可以公平地说，陷阱是一个有趣的想法，但结果并没有产生很大的实际影响。这是研究。那个会发生。