Treap with implicit keys

Question

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".

Forgotten

Answer 1

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

Atmo

The link is dead. – Albur

@CarlosPinzón thanks! updated link – Atmo

Answer 2

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.

Hieratic

I'm talking exactly about treap, not randomized BST. As I see it, treap has keys and priorities: key is the actual user data stored in the tree, and priority is randomly chosen internal parameter. Treap is BST on keys and heap on priorities simultaneously. I'm Ukrainian, lecture was in Russian, lecturer - Vitaly Goldstein, ACM ICPC medal winner, former Google intern, currently works at Yandex. Lecture was heard at the Kharkov winter ACM programming school, if you know it. I'll share some additional explanation about this structure in the UPD of my post. – Forgotten

@Forgotten I'm interested in a writeup of this technique. Please could you send me a link if you have it handy? Thanks! – Cysteine

@Cysteine The original paper on both treaps and randomized BSTs is people.ischool.berkeley.edu/~aragon/pubs/rst96.pdf. But it describes only the basic definition and operations. I've covered all the material on treaps and their applications I'm aware of (including treaps with implicit keys) in the series of three articles: #1, #2, #3. Russian only, unfortunately. – Forgotten

@Forgotten Thanks! Interesting links. I am especially interested in #3 since it is the one that describes how to reverse an array in O(log n) time and I find that an interesting problem to which I don't know the solution. Do you understand the solution presented and can you prove the correctness? – Cysteine

@Cysteine Yes, I do. I wouldn't write an article about something I cannot understand :) The proof should be obvious after reading: basically, #2 and #3 together are the proof, it's described there completely. However, if you want me to sum it up, the description of delayed operations and node annotations won't fit into this comment. – Forgotten

Thanks! This link is easier to understand: e-maxx.ru/algo/treap (got it from a post on Topcoder) – Cysteine

@Cysteine Actually, treap is able to perform lots of interesting operations in O(log n), not only reversing a subarray. But e-maxx hasn't described that (yet?). – Forgotten

@Forgotten yep! It sure seems like it. Basically, this is the first structure that I have seen which can (in expected) O(log n) time splice out a set of elements in a given range. This seems to be the important difference between this and other ordered data structures. – Cysteine

Answer 3

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.

Caliper

Answer 4

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.

Rossini

Can I do merges and splits with any self-balancing tree? Implicit tree allows to split an array at any index, or cut out a subarray, or merge two arrays - all in O(log N) time. Is it true for any other tree: possibility of merging/splitting data structure with maintaining of additional statistics in the nodes: sum/max/size of the subarray, delayed additions/painting/changes/reversing/etc ? – Forgotten