Implementation of a data structure with O(logn) access and O(logn) insertion?

Question

Does anyone know of a data structure where I can access and delete the k-th item in worst case O(logn) and also supports the operation of inserting an item after the k-th item in worst case O(logn)?

Answer 1

Yes. What you describe can be achieved with an augmented tree. Every node has a counter indicating the number of nodes in its subtree (including itself). For leaf nodes, the counter is 1. For the root node, the counter is the total number of nodes. This way, you can find the k-th item with a binary search starting at the root. Whenever you insert/remove an element, you have to update the counters in the path that goes from that position to the root.

This kind of trees have been called order statistic trees, rank trees, counter trees...

You can find an implementation here and another one here.

See chapter 14, "Augmenting Data Structures" in the great book "Intorduction to Algorithms", by Cormen, Leiserson, Rivest and Stein.

Answer 2

If you need integer indexes (as opposed to keys), take a look at rope or deque, which will be essentially O(c) for these operations.

As for associative data structures, a typical hash-table will also be amortized O(c), while a balanced tree will be O(log(n)).