5
$\begingroup$

An array is built starting with an empty array, and then a sequence of insertions:

  1. insert $a_1$ at index $z_1=1$
  2. insert $a_2$ at index $z_2$
  3. insert $a_3$ at index $z_3$
  4. ...

and so on. When we insert element $a_i$ and index $z_i$ the result is that $a_i$ is now at index $z_i$, whereas everything before index $z_i$ is unchanged and everything after has its index increased by 1. (With one-based indexing) E.g., the sequence $(3,1), (5,2), (1,2)$ gives $[3]$ then $[3,5]$ then $[3,1,5]$. All of the instructions will make sense, i.e., $1 \leq z_i\leq i$.

My question is about how to calculate the final array. The naive approach would be to start with an empty array, and literally obey the instructions; but in the language I program, insertions have a worst case time complexity of $O(\# $elements shifted$)$; if, for example, all the insertion indices were $1$, this would result in $O(N^2)$ time.

Supposing we have access to all the instructions simultaneously, how can we calculate the final array in faster than $O(N^2)$ time? I would be happy with a name if this problem is well studied. I did make the following (family of) observations:

  1. the element which ends up at index 1 was the last one which arrived with index 1.
  2. the element which ends up at index 2 arrived with index 1 or 2. If it arrived with index 2, then none came after it with either index 1 or 2. If it arrived with index 1, then exactly one came after it with index 1, after which came none with index 2.
  3. the element which ends up at index 3 arrived with index 1, 2, or 3. If it arrived with index 3, then none came after it with index 1, 2 or 3. If it arrived with index 2, then exactly one element with index 1 or 2 followed it, then none after that with index 1, 2, or 3. If it arrived with index 1, then it was followed by one with index 1, then one with index 1 or 2, and then none after that with index 1, 2, or 3.

... and so on. However I can't think of the algorithms or data structures that would make this information useful.

$\endgroup$
  • $\begingroup$ It looks like your observation could lead to a different solution in $O(n\log n)$. $\endgroup$ – John L. Nov 19 '19 at 23:47
2
+50
$\begingroup$

Prelimiaries

You can augment an AVL tree to support all the usual operations plus the following:

Shift$(a,b)$ increases all keys $k \ge a$ by $b \ge 0$ in $O(\log n)$ time (where $n$ is the number of elements in the tree).

To do so add a value $x_v$ to each node $v$ in the tree. This value represents an offset to be added to all keys stored in the subtree rooted at $v$. The Search, Insert, and Shift operations, along with the required rotations can be implemented as follows (I won't be using the Delete operation, but it can also be implemented).

Search The search operation work as usual except that you now keep track of the cumulative offset in the path from the current node to the root.

Insert To insert a node with key $k$, use the search operation to find the position where a node with key $k$ would need to be placed and the cumulative offset $\overline{x}$ up to that point. Add a leaf in that position and store its key as $k - \overline{x}$. Perform the necessary rotations to rebalance the tree (see the sequel).

Rotations To perform a right rotation on $u$ let $v$ be its left child. "Push down" the offset of $u$ as follows: increment the stored key of $u$ by $x_u$, add $x_u$ to the offsets of the children of $u$, and set $x_u$ to $0$. Similarly, "push down" the offset of $v$. Perform the rotation as usual. Left rotations are symmetric.

Shift$(a,b)$. Find the node $u$ with key $a$ or, if no such node exists, find its successor (if the successor doesn't exist either, we are done). Increase the stored key of $u$ by $b$. If $u$ has a right child $v$ then increase $x_v$ by $b$ as well. Walk from $u$ to the root of the tree. Every time you walk to a vertex $w$ from its left child, increase the key of $w$ by $b$ and the offset $x_z$ of the right child $z$ of $w$ by $b$ (if $z$ exists).


Solving your problem

Keep an augmented AVL tree $T$ and consider the operations one at a time. At the end of the generic $i$-th step, the tree will contain $i$ nodes that collectively store the elements of the first $i$ operations. Each node $u$ is associated with one element of the array. The key of $u$ is exactly the position of $u$'s element in the array, as of the $i$-th operation, while the element's value is stored as satellite data in $u$.

When the operation $(a_i, z_i)$ is to be processed do a Shift$(z_i, 1)$ operation on $T$. Then, insert a new node with key $z_i$ and satellite data $a_i$ in $T$.

At the end of the process you can traverse the tree and recover the final position (the node's key) of each array element (the node's satellite data).

The total time required is $O(n \log n)$.

$\endgroup$
  • $\begingroup$ Your answer has forced me to learn about AVL trees which I have put off for some time. I will need some time before I can try this idea. $\endgroup$ – Matthew C Nov 12 '19 at 3:33
  • $\begingroup$ If I'm getting the point of this, the keys of this tree are meant to be unique (whereas the insertion indices in the original problem may be repeated), so that at the end of every step, we could traverse the tree and the element with key 1 is first, the element with key 2 is second, etc. However, if I follow the steps of this algorithm applied to say, $(5,1), (6,2), (7,3)$, I would need a right rotation at $5$ after insertion of $7$, and the stored key of $5$ becomes $2$, the same as the key of $6$ in your rotation "push-down" step, violating uniqueness. $\endgroup$ – Matthew C Nov 18 '19 at 16:28
  • $\begingroup$ After inserting $(5,1),(6,2),(7,3)$ (but before rebalancing), the tree is unbalanced to the right. All the offsets are $0$. The key stored in the root $r$ is $1$ (with value $5$), the key stored in the right child $u$ of $r$ is $2$ (with value $6$), and the key stored in the right child $v$ of $u$ is $3$ (with value $7$). To rebalance the tree a left rotation rooted at $r$ is needed. The push-down step is a no-op since all the offsets are $0$. The tree from the rotation is balanced and has $u$ as the root, $r$ as $u$'s left child, and $v$ as $u$'s right child. I don't see any problem here. $\endgroup$ – Steven Nov 18 '19 at 18:54
  • $\begingroup$ Ok, I meant to say left rotation and furthermore I chose an example that works fine. I've written out the steps precisely for the sequence of insertions $(1,2,2,2)$ and it shows that you can end up with duplicated keys, using your algorithm: imgur.com/a/eFKZGFg I think it might be true that the key+offset is unique in the tree, but BST requires unique keys. On the other hand, if you were to propagate the change from a new +1 offset, that could be O(n) time as you would need to update the keys of all succeeding values. $\endgroup$ – Matthew C Nov 19 '19 at 0:02
  • $\begingroup$ You seem not to be taking offsets into account when looking at keys. From my answer: "add a value $x_v$ to each node $v$ in the tree. This value represents an offset to be added to all keys stored in the subtree rooted at $v$." In your final tree node $c$ has key $3+ x_c = 3+0=3$, node $a$ has key $1+ x_a + x_c =1+0+0=1$, node $d$ has key "2 + x_d + x_a + x_c = 2+0+0+0", and node $b$ has key $3 + x_b + x_c = 3+1+0 = 4$. The state of the tree seems correct to me. Somehow you're not taking into account $x_b$ when looking at the nodes in the subtree rooted at $b$. $\endgroup$ – Steven Nov 19 '19 at 10:36
0
$\begingroup$

This is an explanation of the correctness of Steven's answer. Of course I would be interested if anyone came up with something simpler but it is a great solution as it stands.

Define the effective key at a node to be the node's label + the offsets of all nodes on the (inclusive) path from itself to the root. Our inductive hypothesis is that after processing the $i$-th insertion, we have $i$ nodes with effective keys $1,2,\ldots, i$, in a balanced BST ordered with respect to effective keys. Physically, the effective key for the node associated with element $a$ equals the current index of element $a$ in our array.

Algorithm, at step $(a_i,z_i)$. By hypothesis, the tree of size $i-1$ has nodes with effective keys $1$ through $i-1$. In the case $z_i=i$ we just locate the unique node with effective key $i-1$ and insert $i$ with offset $0$ as a right child. In the other case, $z_i<i$, we perform SHIFT($z_i,1$); the way that it is defined means that SHIFT$(z_i,1)$ increases the effective key of nodes $z_i, z_i+1, \ldots, i-1$ by precisely 1 and leaves all lesser keys unchanged. To insert the effective key $z_i$, we either put it in the left slot of $z_i+1$, or the rightmost descendant of $(z_i+1).left$; in either case, we store it with label $z_i-(\text{cumulative offset})$ and offset 0. Both SHIFT and this insertion happen in $O(\log N)$ time. Now we have effective keys $1$ through $i$ reprsented in a BST.

So insertions do the right thing to effective keys. Now to keep the BST balanced (and so achieve $\log n$ complexity) AVL and red-black trees use rotations. It is known that rotations preserve the orderings in a BST. The problem here is that the effective keys are calculated using the offsets leading up to the root. A rotation may change the offsets seen on the way from a node to the root, since it may change the path from that node to the root. For instance if the node $v$ is rotated up into $u$'s position, then the offset $x_u$ that would have been counted in the path from root to $v$, is no longer encountered, while the offset $x_v$ would now be counted in the calculation for $u$. To see how we might do rotations without messing up the effective keys, we introduce the "push-down" operation on a node $u$. Let $v_1, v_2$ be its children. The push down on $u$ increments $x_{v_1}$ and $x_{v_2}$ by $x_u$; increments $u$ by $x_u$; and lastly sets $x_u=0$.

During a rotation (let's say right rotation for definiteness) about node $u$ with left child $v$, we first push down $u$, then push down $v$, and finally rotate as usual: it can be seen by checking all modified parts of the tree, that the effective keys remain the same after rotation: enter image description here (in the above picture, we'd check that the effective keys corresponding to nodes $v,u$ and subtrees $R,S,T$ are unchanged).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.