Ищем отсортированную коллекцию.Net с доступом к предыдущим и следующим элементам

Question

Я реализую алгоритм Бентли-Оттмана, который требует для линии развертки (SL) структуру данных со следующими свойствами:

• поддерживать отсортированную коллекцию T, где T является IComparable<T>,
• вставка элементов должна быть O(log count)и должен возвращать, был ли элемент уже вставлен,
• удаление элементов должно быть O(log count),
• для данного элемента e (уже в коллекции или нет) мне нужен предыдущий и следующий элемент коллекции рядом с e в порядке сортировки.

SortedList<TKey, TValue> имеет O(count) при вставке и удалении, поскольку он должен перемещать все последовательные элементы в списке. Тем не менее, я мог бы проиндексировать его, и, следовательно, получить предыдущий и следующий элементы в O(1)раз я знаю индекс e,

SortedDictionary<TKey, TValue> а также SortedSet<T> иметь O(log count) вставка и удаление, но я не могу найти итератор, который дает мне следующий и предыдущий элементы.

Есть ли реализация, которая дает мне полную функциональность?

И если нет, то какой будет самый быстрый способ его реализации? LinkedList<T> не разрешает бинарный поиск. List<T> все еще имеет O(count) вставка / удаление. Я действительно должен реализовать свое собственное сбалансированное дерево?

Answer 1

Например, TreeDictionary библиотеки коллекции C5 и Nuget и Github имеет

bool TryPredecessor(K k, out KeyValuePair res) возвращает true, если существует предшественник k, и в этом случае связывает предшественник с res; в противном случае возвращает false и привязывает значение по умолчанию KeyValuePair к res. Предшественник k - это запись в отсортированном словаре с наибольшим ключом, строго меньшим, чем k, согласно ключу сравнения. Выдает NoSuchItemException, если k не имеет записи предшественника; то есть ни один ключ не меньше k.

и

bool TrySuccessor(K k, out KeyValuePair res) возвращает true, если есть преемник k, и в этом случае связывает преемник с res; в противном случае возвращает false и привязывает значение по умолчанию KeyValuePair к res. Преемник k - это запись в отсортированном словаре с наименьшим ключом, строго большим, чем k, согласно ключу сравнения. Выдает исключение NoSuchItemException, если k не имеет преемника; то есть ни одна запись в словаре не имеет ключа, который больше k.

и должен иметь почти все, что вам нужно.