问题标签 [treap]

现在我一直听说从随机选择的数据构建二叉搜索树比从有序数据构建更快，这仅仅是因为有序数据需要显式重新平衡以将树高度保持在最低限度。

最近我实现了一个不可变的trap，一种特殊的二叉搜索树，它使用随机化来保持自身相对平衡。与我的预期相反，我发现我可以始终如一地从有序数据中构建一个比无序数据快 2 倍并且通常更好地平衡的陷阱——我不知道为什么。

这是我的trap实现：

• http://pastebin.com/VAfSJRwZ

这是一个测试程序：

这是一个比较随机和有序插入时间（以毫秒为单位）的图表：

我在代码中看不到任何使有序输入渐近地比无序输入更快的东西，所以我无法解释其中的区别。

为什么从有序输入构建一个陷阱比随机输入要快得多？

有一种叫做 treap 的数据结构：这是一个随机二叉搜索树，它也是随机生成的所谓“优先级”的堆。

这种结构有一个变体，其中键是隐式的，它们不存储在树中，但我们将树中节点的有序索引视为该节点的键。我们需要在每个节点中存储子树的大小而不是键。这种技术使我们能够将treap视为某种数组，它支持在O(log N)时间内进行大量操作：插入、删除、子数组的反转、间隔变化等等。

我对这个结构有点了解，但没有那么多。我试图用谷歌搜索它，但我发现只有很多关于trap本身的文章，但没有关于这个“隐式treap”/“索引列表”的文章。我什至不知道它的名字，因为我的母语不是英语，而且我听的讲座使用的是母语结构术语，而不是英文原词。这个原生术语可以直接用英文翻译为“隐式键上的Treap”或“隐式键上的笛卡尔树”。

谁能指出关于这个结构的文章或告诉我它的原名？谢谢你。

PS对不起，如果我的英语不够理解。

UPD：关于我正在寻找的结构的一些额外解释。

考虑一个具有随机选择的优先级和键的常见trap，它们是存储在树中的实际用户数据。然后让我们假设我们在每个节点中存储了一些其他用户信息，并且键只是搜索键。下一步是计算和维护每个节点中的子树大小：我们必须在每次 Merge/Split/Add/Remove 之后更新此参数，但它允许我们在 O(log N) 中找到树的第 K 个元素时间。

当我们在每个节点中都有子树大小时，我们可以扔掉键并想象 treap 表示按顺序遍历的用户数据数组。每个元素的数组索引可以很容易地从子树大小计算出来。现在我们可以在数组中间添加/删除一个元素或拆分这个数组——所有这些都在 O(log N) 时间内。

我们还可以进行“多重”操作——例如，为我们的“数组”的所有元素添加一个常量值。为了实现这一点，我们必须使这个操作延迟，在每个节点中添加一个参数，表示一个延迟常量，该常量必须“稍后”添加到该节点子数组的所有元素，并将更改“推”到下为必要的。向子数组添加一个常量或绘制（标记）子数组可以通过这种方式延迟，如反转子数组（这里节点中的延迟信息在位“子数组必须被反转”）等等。

UPD2：这是代码片段- 我发现的少量信息。不要注意西里尔字母 :) 单词“с неявным ключом”在直接翻译中的意思是“带有隐式键”。

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

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

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

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

谢谢你。

我想使用 Treap 结构，但我对这种类型的树不太熟悉。

我有两套，我想写一个方法来将它们与 Treap 进行比较。此方法应返回一个值，该值显示两个集合的相似性。（我的工作是检索一个与输入集最相似的集合）

我该怎么做这项工作？

谢谢

我知道有很多函数可以通过递归调用函数并每次使用节点的根作为左右子树的参数来轻松获取二叉搜索树的高度。但是，当我不在 Treap 上获取参数但它仍然返回一个 int 时，我应该怎么做。我已经能够递归地调用其他方法，但是我停止了这个方法。一些帮助将不胜感激！

这就是我所拥有的，但我在很大程度上认为这是错误的

我的treap有一个procudere删除，在线p=merge(l, merge(m, rs));我有错误error: non-const lvalue reference to type 'nodeptr' (aka 'node *') cannot bind to a temporary of type 'nodeptr' 所以这里是删除和合并的实现

以及我如何将 treap 实现为数据结构。

你能说我，为什么会出现这个错误？我认为一切都很好。对不起，如果问题是nooby。提前致谢。

Prim 的算法是否可以通过 treaps 来实现以加快执行速度，因为正常的堆会在更新键的值时产生问题，同时将顶点存储在堆中，否则需要 O(V) 空间来存储堆中顶点的位置？

我想知道哪种平衡的 BST 很容易用 C++ 编码，并且仍然具有大致等于 O(logn) 的复杂度。

我已经尝试过红黑树，但想要一种代码不太复杂的替代方案。我过去曾与 Treaps 合作过，但我有兴趣探索性能更好或更易于实施的选项。

你有什么建议？

我正在研究trap数据结构。在插入节点时，trap 随机生成节点的优先级。但是如果上图中69个节点生成的优先级是13呢？

父母的优先级必须高于孩子的优先级。treap 的二叉树属性是否与堆属性冲突？

我想知道。谢谢。

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

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

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