Array with fast insertion/deletion

Question

I am looking for a data structure that stores an array of elements and supports these operations:

1. Accessing element at a given index
2. Adding or removing an element at a given index (and hence shifting the following elements)

Arrays do the first operation in O(1) but the second one takes O(n), while linked lists do the opposite. Is there a middle-ground data structure? Say, something that can do both operations in O(lg n) or O(n^epsilon) "worst-case" time?

Note that I am not asking for a balanced binary search tree. Here the keys (indices) are changed and shifted every time a new element is added/removed. For example, removing the smallest element decreases the indices for all other elements by 1.

Answer 1

There is 'AVL-Array', an STL-style container that performs both operations in O(log n).

It is built on top of an AVL-Tree, but it is still not an associative container, but sequential.
It supports index access [] with vector semantics.

Notice that AVL-Array does not implement a search tree, but rather a sequential container that
happens to come in tree form. Indexing, iteration, insertion and deletion all do what you would
expect a vector to do.

You can find it here

Answer 2

You can do this with a kind of balanced binary tree whose in-order traversal gives the array elements in order, i.e., the leftmost node stores A[0] and the rightmost node stores A[n-1], where n is the number of elements in the array.

At each node we will store the total size s of the sub-tree rooted at that node (i.e. the total number of nodes), the value v of the array element stored at that node, the left child l of the node, and the right child r of the node.

You can retrieve the value of A[i] from such a tree as follows (for simplicity of exposition, no error conditions are checked):

int get_element(node *n, int i) {
  int ls = (n->l == NULL) ? 0 : (n->l)->s;

  if (i < ls) return get_element(n->l, i);
  else if (i == s) return n->v;
  else return get_element(n->r, i-(ls+1));
}

If the tree is balanced, this will take O(log n) time. Inserting at an index or deleting at an index is similar to any balanced tree scheme, except that you are using the sub-tree sizes to navigate rather than the key value, which will also take O(log n). Balanced tree data structures generally use a "rotation" to restore balance, e.g., a right rotation:

   y o                  o x  
    / \                / \   
 x o   C     ==>      A   o y
  / \                    / \ 
 A   B                  B   C

We can maintain the size of the new subtree at node y as size(B)+size(C)+1, and then that of x as size(A)+size(y)+1.

If you use the ideas from the finger search tree then you will also be able to iterate through the whole array in O(n), iterate through a sequence of length k in O(k), and skip forward or back from A[i] to A[i+k] or A[i-k] in O(log k).