C # logarithmic time

Question

Is there a .NET implementation for a list collection in such a way that both insert and search are the worst O (log (n)) operations? By default, the System.Collections.Generic.List ' Insert ' method is an O (n) operation.

In the collection of lists, I mean a massive extensible data structure. By "lookup" I mean access by index.

I suspect that this can be done using balanced trees, but it would be non-trivial to implement.

Answer 1

I don't know the .NET implementation, but the data structure that might work for you is an indexable skipist. It has similar O (log n) performance, like a balanced binary tree, but conceptually looks more like a linked list.

http://en.wikipedia.org/wiki/Skip_list

I don’t think writing in C # would be too difficult.

Answer 2

C5 TreeSet should give you a red / black implementation with these characteristics, including index access.

Answer 3

I don’t know if the .net infrastructure exists, but you can implement aa tree insert and search - this is O (log n).

Answer 4

There is no possible solution for this if you need to access the fields using their index. You can use SortedList, but then you get O (n), or you can use SortedDictionary, but then you lose access to the array (by index).