Is there a data structure to keep a list of elements (not necessarily sorted) that performs the Access (by index) and Insert operations in a reasonable asymptotic time?
When I say "reasonable time", I mean that it should be equal to or better than $O(\log N)$.
I'm looking for a structure similar to a dynamic array, but I need a better behavior in the Insertion operation. When the array size grows, the time grows exponentially (Except at the end of the array).
Asked By : vicentazo
Answered By : D.W.
A balanced binary tree should meet your needs. You can achieve $O(\lg n)$ time for both operations, as long as the tree is kept reasonably balanced.
To support the "access by index" operation, you can augment the tree so that each internal node contains the number of children underneath it. Insert operations still take $O(\lg n)$ time (find the place where to insert a new leaf, then traverse the path from that leaf to the root, incrementing the counter in each such node). The "access by index" operation can be done using the counts in each node; they tell you at each stage whether to recurse to the left child or right child.
There are probably other data structures as well, but this should meet all of the requirements you listed.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/13598
0 comments:
Post a Comment
Let us know your responses and feedback