Sorted Structure/constant ith item access time

[Hiiip]

Hello,

I am looking for a structure that allows me to:

1. Append in O(logN) or better
2. Delete in O(logN) or better
3. Access the ith item in O(1)

I don't need any other operations

In addition, new items are always greater (>) than existing items (the structure is always sorted) and no item appears twice.

Maybe, I think it is impossible...

[toraj58]

c# SortedDictionary removal and insertion and retrieval is O(log n)

see more information here and some comparison between c# SortedDictionary and SortedList.

MSDN:
http://msdn.microsoft.com/en-us/library/ms132319.aspx

what do you mean by access O(1) i think it is not possible !
if you mean access by KEY, index all Array-Like structures apply to it but something like any kind of Linked-List (recursive-Two way- with header/ without header) don't apply to it.

[Hiiip]

Deletion and Append O(N), Access O(1), that is an array.

You can improve the first two to O(logN) by making access more expensive. For any kind of item. I know that.

What I want, is to make the first two cheaper, but keeping access at O(1), by abusing the fact that I only need delete/append (and not insert). and the values are increasing. If it's possible...

[laserlight]

If you use a sorted array, append would also be in O(1) due to the nature of your data, but deletion not at the end would still be in O(n).

[Hiiip]

That's right, I meanto to say Deletion and Insertion are O(N).


Basically what I am trying to avoid is the effect that deleting at the start requires moving all items in front to move one back. But I guess there is no way around it if you want to keep access at O(1).

What about something like

n items, m (already done) deletions, or gaps

O(m) access, O(1) append, O(logN) delete... possible? hmm

[pm_kirkham]

Are those worst case or average?

The primary operations of a VList are:
* Locate the kth element (O(1) average, O(log n) worst-case)
* Add an element to the front of the VList (O(1) average, with an occasional allocation)
* Obtain a new array beginning at the second element of an old array (O(1))
* Compute the length of the list (O(log n))

You haven't specified whether it's deletiog from one end, from either end or from the middle you want to be scalable.

[Hiiip]

Deletion from everywhere.

I had a look at VLists, but it seems a bit flawed. What happens if you delete lots of elements in the middle? The VList will turn into a linked list? Or is there some magical "rebalancing" going on? I will read the paper on it.

Also, if you have 2^20 elements, in the first node there will be 2^10 items. What happens if you delete the 2^9th element? Still need to move lots of elements.