Ordered sequence with logarithmic insert and remove

Question

Problem: we have a sequence of numeric values, e.g. [102, 25, 77, 17, 2, 13]. We need to implement 3 operations, each can be at most logarithmic time complexity.

1. insert(i, v) - inserts value v at index i.
2. remove(i) - removes value at index i.
3. peek(i) - returns value at index i.

What I've tried: AVL tree, where node keys are elements' indices. It theoretically guarantees log time for all three operations. The problem is when we use e.g. insert(0, v), we need to update all of the other indices (we want to keep the proper order), resulting in O(n) complexity. Sample sequence would look like this in my way of thinking:

Answer 1

I think you have already a good idea with AVL trees.

To improve the data structure, you should keep track of the size of each subtree (and discard indices, they are not really useful here).

In details, a node $x$ of the tree should have the following information:

• value;
• size;
• height;
• pointer to the left child;
• pointer to the right child.

There is no key in there, since those trees are not binary search trees, but the values are ordered by increasing indices when considering the in-order (like the keys in a BST). However, since the indices may change during the process, as you have stated, there is no use in storing those.

Peeking is the easiest algorithm:

define a.peek(i):
   s ← a.left.size
   if s = i then return a.value
   if s > i then return a.left.peek(i)
   return a.right.peek(i - s - 1)

To insert an element at position $i$, we search the position the same way as the peeking is done and continue in the left or right child (eventually with the node it replaces). All size and heigths or ancestors must be modified and some rotations may be necessary to keep the balance of each node.

define a.insert(i, v):
   if a is empty then
      a.value ← v
      a.size ← 1
      a.height ← 0
      a.left ← empty
      a.right ← empty
      return
   s ← a.left.size
   if s = i then
      if a.left.height < a.right.height then
         a.left.insert(i, v)
      else
         a.right.insert(0, a.value)
         a.value ← v
      a.size ← a.size + 1
      a.height ← 1 + max(a.left.height, a.right.height)
   else if s > i then
      a.left.insert(i, v)
      a.size ← a.size + 1
      a.height ← 1 + max(a.left.height, a.right.height)
      if a.left.height > a.right.height + 1 then
         do a right rotation
   else
      //similar insertion in the right child

When deleting a node, it need to be replaced. The easiest way to do it is to use a node in the child of greatest height, either the rightmost node in the left child or the leftmost node in the right child. Implementation left to you.

All those operations have time complexity linear in the height of the tree, which is logarithmic in the size, given that the balance is keeped.

Answer 2

You need to augment the AVL tree with weight information on every node (i.e. the number of nodes in the subtree rooted there).

Insertion and deletion will require to increment/decrement the weights of all nodes from the root to the insertion/deletion point.

Lookup will use the weight information to choose the descent directions.

Note that the index information remains implicit.

Searching for index $3$:

After deletion: