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

Answer 1

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.

Answer 2

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.

Answer 3

You can find this data structure in the paper by Kaplan and Verbin on sorting signed permutations by reversals (page 7, section 3.1): http://www.math.jussieu.fr/~fouquet/ENSEIGNEMENT/PROJETS/kaplan.pdf.

Answer 4

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.