0
$\begingroup$

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 ..

$\endgroup$
2
  • $\begingroup$ Worst-case or amortized worst-case? $\endgroup$ – Jörg W Mittag Sep 13 '20 at 18:31
  • $\begingroup$ worst case only $\endgroup$ – harsha kunchala Sep 13 '20 at 18:46
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.