# Data structure that allows accessing elements by index and delete them in O(logn)

I need to take an kth index element from array like data structure and delete it (k is any possible index). Array have O(n) for deleting elements, and List have O(n) for searching element. I would like to do both operations in O(logn) time.

Which data structure should I use to meet this requirement?

Clarification:

Deleting element on index(5) will move element from index(6) to index(5)

the element at index 6 change indexes so that it now has index 5 and 7th element changes to 6th so on ..

• Worst-case or amortized worst-case? Sep 13, 2020 at 18:31
• worst case only Sep 13, 2020 at 18:46

Take any self-balancing binary tree (e.g. AVL) and replace every node's key with the number of left descendants it has. This is easy to keep up-to-date for tree insertions/deletions (in $$O(log n)$$ time), and rotations (in $$O(1)$$ time).
Then to find the node with index $$i$$ you start at the root and repeatedly compare $$i$$ with the value of the current node $$v$$. If $$i < v$$ you go to the left child, $$i = v$$ you found the correct node and $$i > v$$ you subtract $$i := i - v$$ and go to the right child.