Treap与隐含的钥匙

Question

有一个数据结构称为treap:这是一个随机的二进制的搜索树，这也是一堆随机产生的所谓"优先权".

有一个变化中的这种结构，在那里键是隐含的，他们不是储存在树，但是我们考虑的有序的指数点在树作为这个节点的关键。我们需要储存大小的子树在每个节点，而不是关键。这种技术使我们能够考虑treap像是某种阵列，它支持许多操作O(日志N)时间：插入、删除、回归的子阵列，改变上的间隔等等。

我知道一些关于这种结构,但没有那么多。我试着歌，但我们发现，只有很多文章关于treap本身，但没有关于这种"隐treap"/"索引列表"。我甚至不知道它的名字，因为我的母语不是英语和讲座的我已经听取了使用母语的结构，没有英文原文的术语。这种本地语可以直接翻译成英文为"Treap在隐式钥匙"或"笛卡尔树上隐含的钥匙"。

任何人都可以点我在本篇关于这个结构或者告诉我其原来的名字吗？谢谢你。

P.S.对不起如果我的英语不是可以理解的不够的。

UPD： 一些额外的解释有关的结构以我要找的。

考虑一个通常的treap与随机选择的优先事项和钥匙，它们实际用户的数据储存在树。然后让我们来想象一下我们有一些其他的用户信息存储在每个节点，并键是没有但是搜索键。下一步是计算和维持子树大小在每个节点：我们有来更新这个参数之后，每一个合并/分割/Add/删除，但它使我们能够找到，例如，Kth元的树O(日志N)的时间。

当我们的子树大小在每个节点上，我们可以把钥匙掉和想象一下，treap表示一系列的用户数据在序遍历。阵列的索引的每个元素可以很容易地计算从树大小。现在我们可以添加、删除一个元素中的阵列，或者分裂该阵列所有在O(日志N)的时间。

我们也可以使"多"操作，例如，增加一个常数值中的所有元素的我们的"阵列".要实现这一点，我们必须使这种操作延迟，加入一个参数在每个节点代表着一个延迟的不断需要"之后"加入的所有要素的这个节点的子阵列，并且"推动"改变了以下必要的。增加一个常量子阵或绘画(标记)的子阵列可以由延迟的，在这种方式，为扭转子阵列(这里的延误信息的节点位"子阵列必须扭转")，等等。

UPD2： 这里的 代码 -片的少量信息，我发现。没有注意到西里尔文:)话"с неявным ключом"意味着直接翻译"有隐含的钥匙"。

Answer 1

您可以在Kaplan和Verbin的论文中找到此数据结构，以通过逆转对签名的排列进行排序（第7页，第3.1节）： http://www.math.jussieu.fr/~fouquet/enseignement/projets/kaplan.pdf.

Answer 2

对关键的概念(没有双关的意！) 在treaps是使用钥匙，这是随机的。如果你移除的钥匙，我不要看你怎么可以有一个treap:所以也许我误解了你的问题。或许你指的替代treaps， 随机的二进制的搜索树.这两个数据结构使用相同的想法，你可以达到的平均情况的复杂性，通过确保你的树看起来像一个普树(而不是一种病态的情况下)。

与treaps，你这样做使用随机的优先事项和平衡。

随机的二进制树木中，随机性是仅包括在建设：也就是说，当你插入一个节点在树T，它概率为1/(size(T)+1)在根，那里的大小(T)数量的节点的T；当然，如果节点不是插在根，你继续递归直到它为增加。(看我的文章C。马丁内斯一详细研究这些树木。)

这个数据结构的行为完全像一个treap，但使用不同的机制，不需要钥匙。

如果这不是你要找的是什么，也许你可以分享一些额外的信息：你讲师提到谁可能曾在这个结构，这里没有你在这里的讲师和什么他/己的国籍。它可能似乎并不喜欢它，但我们知道你的母语可能是一个重要的线索你可以一般peg下来的算法/数据结构的一个特定的国家，起源于它。

Answer 3

也许您正在寻找 绳索 （字符串的复杂形式）修改为您对延迟操作的需求。有趣的是，关于绳索有一个公开的问题 此时此刻.

Answer 4

我认为该数据结构没有一个名称，因为它只是两个正交概念的组合。您可以使用类似的隐式键，几乎可以使用任何自动平衡的树数据结构。

您可能需要看一下替罪羊树，因为它们已经使用了子树大小进行重新平衡，并且不需要每节点开销。