使用隐式键进行处理
有一种称为treap的数据结构：这是一个随机二叉搜索树，它也是随机生成的所谓“优先级”的堆。
这种结构有一个变体，其中键是隐式的，它们不存储在树中，但我们将树中节点的有序索引视为该节点的键。我们需要存储每个节点中子树的大小而不是键。这种技术使我们能够将 treap 想象成某种数组，它支持 O(log N) 时间内的大量操作：插入、删除、子数组的反转、按时间间隔更改等。
我对这个结构有一点了解，但不是很多。我尝试用谷歌搜索它，但我只找到了很多关于treap本身的文章，但没有找到关于这个“隐式treap”/“索引列表”的文章。我什至不知道它的名字，因为我的母语不是英语，而且我听的讲座使用的是母语结构术语，而不是英语原始术语。这个原生术语可以直接翻译成英文“Treap on theimplicitkeys”或“Cartesiantreeontheimplicitkeys”。
有人可以指点我有关该结构的文章或告诉我它的原始名称吗？谢谢。
PS 抱歉，如果我的英语不够明白。
UPD：关于我正在寻找的结构的一些额外解释。
考虑一个具有随机选择的优先级和键的常见陷阱，它们是存储在树中的实际用户数据。然后，假设我们在每个节点中存储了一些其他用户信息，而键只是搜索键。下一步是计算和维护每个节点中的子树大小：我们必须在每次合并/拆分/添加/删除后更新此参数，但它允许我们在 O(log N) 中找到例如树的第 K 个元素时间。
当每个节点都有子树大小时，我们可以扔掉键并想象treap代表中序遍历的用户数据数组。每个元素的数组索引可以很容易地从子树大小计算出来。现在我们可以添加/删除数组中间的元素或拆分该数组 - 所有这些都在 O(log N) 时间内完成。
我们还可以进行“多个”操作 - 例如，向“数组”的所有元素添加一个常量值。为了实现这一点，我们必须延迟此操作，在每个节点中添加一个表示延迟常量的参数，该常量必须“稍后”添加到该节点子数组的所有元素中，并将更改从上到下“推”为必要的。向子数组添加常量或绘制（标记）子数组可以通过这种方式延迟，如反转子数组（此处“子数组必须反转”位中的节点中的延迟信息）等等。
UPD2：这是代码片段 - 一小部分我找到的信息量。不要注意到西里尔语:)单词“с неявным ключом”在直接翻译中的意思是“使用隐式密钥”。
There's a data structure called treap: that's a randomized binary search tree, which is also a heap on randomly generated so-called "priorities".
There's a variation of this structure, where keys are implicit, they aren't stored in the tree, but we consider the ordered index of the node in the tree as this node's key. We need to store size of subtree in each node instead of key. This technique enables us to think about treap like some kind of array, which supports lots of operation in O(log N) time: insertion, deletion, reversion of subarray, changing on interval and so on.
I know a bit about this structure, but no so much. I tried to google it, but I've found only lots of articles about treap itself, but nothing about this "implicit treap" / "indexed list". I even don't know its name, because my native language isn't English and lecture I've listened used the native term of structure, not English original term. This native term can be directly translated in English as "Treap on the implicit keys" or "Cartesian tree on the implicit keys".
Can anybody point me at the article about this structure or tell me its original name? Thank you.
P.S. Sorry if my English wasn't understandable enough.
UPD: Some extra explanation about structure I'm looking for.
Consider a usual treap with randomly chosen priorities and keys, which are actual user data stored in the tree. Then let's imagine we have some other user info stored in every node, and keys are nothing but the search keys. Next step is calculating and maintaining the subtree size in each node: we have to update this parameter after every Merge/Split/Add/Remove, but it allows us to find, for example, Kth element of the tree in O(log N) time.
When we have subtree sizes in each node, we can throw keys away and imagine that treap represents an array of user data in inorder traversal. Array index of each element can be easily calculated from subtree sizes. Now we can add/remove an element in the middle of array or split this array - all in O(log N) time.
We can also make "multiple" operation - for example, add a constant value to all elements of our "array". To implement this, we have to make this operation delayed, add a parameter in every node that represents a delayed constant which has to be "later" added to all the elements of this node's subarray, and "push" the changes up to down as necessary. Adding a constant to subarray or painting (marking) the subarray can be made delayed in this way, as reversing the subarray (here the delayed info in the node in the bit "subarray has to be reversed"), and so on.
UPD2: Here's code snippet - piece of the small amount of information I've found. Don't notice cyrillic :) Words "с неявным ключом" mean in direct translation "with implicit key".
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
您可以在 Kaplan 和 Verbin 撰写的关于通过反转对有符号排列进行排序的论文中找到此数据结构（第 7 页，第 3.1 节）：https://www.sciencedirect.com/science/article/pii/S0022000004001503
You can find this data structure in the paper by Kaplan and Verbin on sorting signed permutations by reversals (page 7, section 3.1): https://www.sciencedirect.com/science/article/pii/S0022000004001503
treaps 的关键思想（没有双关语！）是使用随机的密钥。如果你取下钥匙，我不明白你怎么能有一个陷阱：所以也许我误解了你的问题。或者您可能指的是 Treap 的替代方案，随机二叉搜索树。这两种数据结构都使用相同的想法，即通过确保您的树看起来像普通树（而不是病理情况），您可以获得平均情况的复杂性。
对于陷阱，您可以使用随机优先级和平衡来做到这一点。
对于随机二叉树，随机性仅包含在构建过程中：也就是说，当您在树 T 中插入一个节点时，它有概率 1/(size(T) + 1) 位于根，其中 size(T)是T的节点数；当然，如果该节点未插入到根节点，则继续递归，直到添加该节点。 （有关这些树的详细研究，请参阅我的 C. Martinez 的文章。）
此数据结构的行为与 Treap 完全相同，但使用了不需要密钥的不同机制。
如果这不是您想要的，也许您可以分享一些额外的信息：您的讲师是否提到过可能参与过此结构的任何人，这位讲师您在哪里以及他/您的国籍。看起来可能不是这样，但了解你的母语可能是一个重要的线索，因为你通常可以将算法/数据结构与起源它的特定国家联系起来。
The key idea (no pun intended!) in treaps is to use keys, which are randomized. If you remove the keys, I don't see how you can have a treap: so perhaps I misunderstood your question. Or perhaps you are referring to the alternative to treaps, the randomized binary search tree. Both data structures use the same idea that you can attain average-case complexity by making sure your tree looks like an average tree (instead of a pathological case).
With the treaps, you do this using random priorities and balancing.
With randomized binary trees, the randomness is solely included during the construction: that is, when you insert a node in tree T, it has probability 1/(size(T) + 1) to be at the root, where size(T) is the number of nodes of T; and of course if the node is not inserted at the root, you continue recursively until it is added. (See articles my C. Martinez for a detailed study of these trees.)
This data structure behaves exactly like a treap, but uses a different mechanism that does not require keys.
If this is not what you were looking for, perhaps you could share some additional information: did your lecturer mention anybody who might have worked on this structure, where did you here this lecturer and what his/your nationality. It might not seem like it, but knowing your native tongue could be an important clue as you can generally peg down algorithms/data structures to a specific country that originated it.
也许您正在寻找一个绳子（复杂形式的字符串）修改为您的延迟操作的需求。有趣的是，有一个关于绳索的悬而未决的问题现在就在< /a>.
Maybe you are looking for a Rope (complex form of string) modified to your needs for delayed operations. Interesting thing is that there is an open question regarding ropes right here right now.
我认为该数据结构没有名称，因为它只是两个正交概念的组合。您可以将这样的隐式键与任何自平衡树数据结构一起使用。
您可能想看看替罪羊树，因为它们已经使用子树大小进行重新平衡，并且不需要任何每个节点的开销。
I don't think there is a name for that data structure since it is simply a combination of two orthogonal concepts. You could use implicit keys like this with just about any self-balancing tree data structure.
You might want to take a look at Scapegoat trees, since they use the subtree size already for rebalancing and do not require any per-node overhead.