data-structures - 何时使用陷阱

Question

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

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

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

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

谢谢你。

Answer 1

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

考虑以 AVL-tree 或 rb-tree 实现的项目顺序集。以不同顺序插入项目通常最终会生成具有不同形状的树（尽管它们都是平衡的）。对于给定的内容，无论历史如何，trap 都将始终具有相同的形状。

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

1. 安全原因。treap 不能包含有关历史的信息。
2. 高效的子树共享。我见过的最快的集合操作算法使用treaps。

Answer 2

我无法为您提供任何真实世界的示例。但是我确实使用traps来解决编程竞赛中的一些问题：

• http://poj.org/problem?id=2761
• http://poj.org/problem?id=3481

这些实际上不是真正的问题，但它们是有道理的。

Answer 3

您可以将其用作基于树的地图实现。根据应用程序，它可能会更快。几年前，我自己（在 Java 中）实现了一个 Treap 和一个 Skip 列表，只是为了好玩，并做了一些基本的基准测试，将它们与 TreeMap 进行比较，而 Treap 是最快的。你可以在这里看到结果。

例如，与红黑树相比，它的最大优势之一是非常容易实现。但是，据我记得，与红黑树相比，它的操作没有保证成本（搜索是 O(log n) 的high概率），这意味着您将无法使用它在需要特定时间限制的安全关键应用中。

Answer 4

Treaps 是平衡二叉搜索树的变体。确实存在许多算法来平衡二叉树，但其中大多数都是可怕的事情，需要处理大量的特殊情况。另一方面，编写 Treaps 非常容易。通过利用一些随机性，我们得到了一个预期为对数高度的 BBT。使用 treaps 解决的一些好问题是 - http://www.spoj.com/problems/QMAX3VN/ （简单级别） http://www.spoj.com/problems/GSS6/ （中等级别）

Answer 5

Treap 中的任何子树也是一个 Treap（即也满足 BST 规则以及最小或最大堆规则）。由于这个属性，一个有序列表可以很容易地拆分，或者使用 Treaps 可以很容易地合并多个有序列表，而不是使用 RB 树。实施更容易。设计也更容易。

Answer 6

假设您有一家公司，并且您想创建一个库存工具：

• 能够（有效地）按名称搜索产品，以便您可以更新库存。

• 随时获取库存最少的产品，以便您能够计划下一个订单。

处理这些需求的一种方法是使用两种不同的数据结构：一种用于按名称进行有效搜索，例如哈希表，另一种用于获取最迫切需要重新供应的项目的优先级队列。您必须设法协调这两种数据结构，并且您将需要两倍以上的内存。如果我们根据名称对条目列表进行排序，我们需要扫描整个列表以找到另一个标准的给定值，在这种情况下，库存数量。此外，如果我们使用一个最小堆，其顶部是稀缺产品，那么我们将需要线性时间来扫描整个堆以寻找要更新的产品。

特雷普

Treap 是树和堆的混合体。这个想法是强制执行 BST 对名称的约束，以及堆对数量的约束。

产品名称被视为二叉搜索树的键。

相反，库存数量被视为堆的优先级，因此它们定义了从上到下的部分排序。对于优先级，像所有堆一样，我们有一个部分排序，这意味着只有从根到叶的同一路径上的节点才根据它们的优先级排序。在上图中，您可以看到子节点的库存数量始终高于其父节点，但兄弟节点之间没有排序。