Lecture
Consider the dynamic array data structure. In its standard implementation we can append an element to the end of the vector, find out the value of the element at a given position, change an element by its index, and remove the last element. Suppose we need a data structure with the properties above, plus the following operations: insert an element at any position (with the corresponding renumbering of the elements) and remove any element (also with the corresponding renumbering). Such a structure can be implemented on the basis of a treap, and the result is often called a treap with an implicit key.
As is known, a treap is a data structure combining a binary search tree and a binary heap. To implement a treap with an implicit key, we modify this structure. Namely, we keep in it only the priority Y, and instead of the key X we use the following quantity: the number of elements in our structure that lie to the left of our element. In other words, we take the key to be the ordinal position of our element in the tree, decreased by one.
Note that this preserves the structure of a binary search tree with respect to this key (that is, the modified treap remains a treap). However, this approach introduces a problem: the operations of adding and removing an element can change the numbering, and with a naive implementation, updating all the keys would take O(n) time, where n is the number of elements in the tree.
This problem is solved quite simply. The main idea is that this key X is not itself stored anywhere. Instead, we store an auxiliary quantity C: the number of vertices in the subtree of our vertex (the vertex itself is included in the subtree). Note that all operations on an ordinary treap were performed from the top down. Also note that if, along the path from the root to some vertex, we sum up all such quantities for the left subtrees we did not go into, each increased by one, then upon reaching the vertex itself and adding to this sum the number of elements in its left subtree, we get exactly its key X.
The structure of an ordinary treap is maintained using two operations: split — splitting one treap into two such that in one the key X is smaller than a given value, and in the other it is larger, and merge — merging two trees, in one of which all keys X are smaller than in the second. Taking into account the differences between a treap with an implicit key and an ordinary one, the operations are now described as follows: split(root,t) — splitting the tree into two so that the left one ends up with exactly t vertices, and merge(root1,root) — merging any two trees, respectively.
Suppose the split procedure is launched at the root of the tree with the requirement to cut off k vertices from the tree. It is also known that the left subtree of the vertex has l vertices, and the right one has r. Consider all possible cases:
Pseudocode:
⟨⟨Treap, Treap ⟩ split(Treap t, int k)
if t == ∅
return ⟨ ∅, ∅ ⟩
int l = t.left.size
if l ⩾ k
⟨t1, t2⟩ = split(t.left, k)
t.left = t2
update(t)
return ⟨t1, t ⟩
else
⟨t1, t2⟩ = split(t.right, k - l - 1)
t.right = t1
update(t)
return ⟨t, t2⟩
Let us look at any implementation of the merge procedure. Note that it never accesses the key X. Therefore the implementation of the merge procedure for a treap with an implicit key will not differ at all from the implementation of the same procedure for an ordinary treap.
The only action needed to ensure the correctness of these values is that after any operation on a vertex's children, its field C must be set to the sum of these values in its new children, increased by one.
Pseudocode:
void update(Treap t) t.size = 1 + t.left.size + t.right.size
Thus, we have described a structure from which we can cut off a part of arbitrary length on the left and merge any two parts into one in the required order. We are now able to:
Comments