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

Question

我正在实现 Bentley-Ottman algorithm这需要扫描线 (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

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

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.

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