寻找可以访问上一个和下一个元素的 .Net 排序集合

Question

我正在实施 Bentley-Ottman algorithm，它需要扫描线 (SL) 具有以下属性的数据结构：

• 维护 T 的排序集合，其中 T 是 IComparable<T>，
• 插入元素应该O(log count)，并且应该return元素是否已经插入，
• 删除元素应该是O(log count),
• 对于给定的元素 e（无论是否已经在集合中）我需要集合的上一个和下一个元素在排序顺序中紧挨着 e。

SortedList<TKey, TValue> 在插入和删除时有一个 O(count)，因为它必须移动列表中的所有连续元素。但是，我可以索引它，因此一旦我知道 e.

的索引，就可以得到 O(1) 中的上一个和下一个元素

SortedDictionary<TKey, TValue> 和 SortedSet<T> 有 O(log count) 插入和删除，但我找不到任何迭代器给我下一个和上一个元素。

是否有任何实现可以提供完整的功能？

如果没有，最快的实施方式是什么？ LinkedList<T> 不允许二进制搜索。 List<T>还有O(count)insertion/deletion。我真的必须实现自己的平衡树吗？

Answer 1

例如 c5 collection library and nuget and github 的 TreeDictionary 有一个

bool TryPredecessor(K k, out KeyValuePair res) returns true if there is a precedessor of k and in that case binds the predecessor to res; otherwise returns false and binds the default value of KeyValuePair to res. The predecessor of k is the entry in the sorted dictionary with the greatest key strictly less than k according to the key comparer. Throws NoSuchItemException if k does not have a predecessor entry; that is, no key is less than k.

和一个

bool TrySuccessor(K k, out KeyValuePair res) returns true if there is a successor of k and in that case binds the successor to res; otherwise returns false and binds the default value of KeyValuePair to res. The successor of k is the entry in the sorted dictionary with the least key strictly greater than k according to the key comparer. Throws NoSuchItemException if k does not have a successor; that is, no entry in the dictionary has a key that is greater than k.

并且应该拥有您需要的几乎所有东西。