data-structures - 何时使用陷阱

Question

任何人都可以提供真实的例子，说明什么时候存储数据的最佳方式是 treap？

我想了解在哪些情况下 treap 会比堆和树结构更好。

如果可能，请提供一些真实情况的例子。

我试图在这里和通过谷歌搜索搜索使用 treaps 的案例，但没有找到任何东西。

谢谢你。

Answer 1

如果哈希值用作优先级，则 treaps 提供内容的唯一表示。

考虑作为 AVL-tree 或 rb-tree 实现的一组订单项。以不同的顺序插入项目通常最终会形成不同形状的树(尽管它们都是平衡的)。对于给定的内容，无论历史如何，收获将始终具有相同的形状。

我已经看到了为什么唯一表示可能有用的两个原因:

安全原因。 treap 不能包含历史信息。

高效的子树共享。我见过的最快的集合运算算法是使用 treaps。