Рекомендовать отсортированную коллекцию для поиска ближайшего значения слева и справа

Question

Есть ли готовая структура данных в .NET 3.5 для выполнения следующих действий

хранить значения, отсортированные по десятичному ключу, допускается повторное копирование

получить следующее значение (перечислитель), ближайшее к указанному ключу слева и справа

Пример:

Автосалон имеет автомобили, клиент просит найти самую дорогую машину, но дешевле, чем 1000 $

Answer 1

Вы ищете двоичное дерево, позволяющее дублировать ключи (он же multi-set ).В библиотеке .NET таких вещей нет, но их легко реализовать (и они свободно доступны, например, здесь или здесь ).

См. Также Существуют ли реализации мультимножества для .Net?

Answer 2

Я знаю, что вы ищете готовые конструкции, но один вариант, который стоит изучить, - это van Emde Boas Tree . Эта структура дает вам поиск, найти преемника, найти предшественника и удалить все в O (LG LG N), время, которое экспоненциально быстрее, чем сбалансированное дерево поиска. Я не знаком с какими-либо реализациями этой структуры в C #, но это, вероятно, асимптотически оптимальный способ решения вашей проблемы. Если вы храните большое количество целых чисел, оно также может быть очень компактным.

Answer 3

Вы просто используете список, чтобы сохранить цену автомобиля и сортировать ее каждый раз, когда добавляете цену нового автомобиля.

List<int> PriceList= new List<int>();
PriceList.Sort();

Answer 4

Я рекомендую вам использовать SQLite для таких запросов. И ваш запрос будет:

from car in cars where car.Price < 1000 
order by car.Price descending
select car