Логарифмическое время C # list

Question

Существует ли реализация для .NET коллекции списков, в которой операции вставки и поиска являются операциями O (log (n)) в худшем случае?Метод по умолчанию System.Collections.Generic.List ' Insert ' является операцией O (n).

Под коллекцией списков я имею в виду массивоподобныйрасширяемая структура данных.Под «поиском» я подразумеваю доступ по индексу.

Я подозреваю, что это можно сделать с помощью сбалансированных деревьев, но реализовать его будет нетривиально.

Answer 1

Я не знаю о реализации .NET, но структура данных, которая могла бы работать на вас, - это индексируемый пропускаемый список.Он имеет аналогичную производительность O (LG N), как сбалансированное двоичное дерево, но концептуально больше похож на связанный список.

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

Я не думаю, что было бы слишком сложно написатьодин в C #.

Answer 2

C5 TreeSet должен дать вам красно-черную реализацию с этими характеристиками, включая индексный доступ.

Answer 3

Не знаю, существует ли в .net framework, но вы можете реализовать aa tree insert и search - O (log n).

Answer 4

Нет никакого возможного решения для этого, если вам нужно получить доступ к полям, используя их индекс. Вы можете использовать SortedList, но затем вы получите O (n), или вы можете использовать SortedDictionary, но тогда вы потеряете подобный массиву доступ (по индексу).