Data structure that supports random access by index and key, insertion, deletion in logaritmic time with order maintained

Question

I'm looking for the data structure that stores an ordered list of E = (K, V) elements and supports the following operations in at most O(log(N)) time where N is the number of elements. Memory usage is not a problem.

• E get(index) // get element by index
• int find(K) // find the index of the element whose K matches
• delete(index) // delete element at index, the following elements have their indexes decreased by 1
• insert(index, E) // insert element at index, the following elements have their indexes increased by 1

I have considered the following incorrect solutions:

• Use array: find, delete, and insert will still O(N)
• Use array + map of K to index: delete and insert will still cost O(N) for shifting elements and updating map
• Use linked list + map of K to element address: get and find will still cost O(N)

In my imagination, the last solution is the closest, but instead of linked list, a self-balancing tree where each node stores the number of elements on the left of it will make it possible for us to do get in O(log(N)).

However I'm not sure if I'm correct, so I want to ask whether my imagination is correct and whether there is a name for this kind of data structure so I can look for off-the-shelf solution.

Answer 1

The closest data structure i could think of is treaps.

Implicit treap is a simple modification of the regular treap which is a very powerful data structure. In fact, implicit treap can be considered as an array with the following procedures implemented (all in O(logN)O(log⁡N) in the online mode):

1. Inserting an element in the array in any location
2. Removal of an arbitrary element
3. Finding sum, minimum / maximum element etc. on an arbitrary interval
4. Addition, painting on an arbitrary interval
5. Reversing elements on an arbitrary interval

Using modification with implicit keys allows you to do all operation except the second one (find the index of the element whose K matches). I'll edit this answer if i come up with a better idea :)