2

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

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

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

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

是否有任何实现可以为我提供全部功能？

如果没有，实现它的最快方法是什么？LinkedList<T>不允许二分查找。List<T>仍然有O(count)插入/删除。我真的必须实现自己的平衡树吗？

4

1 回答 1

5

例如c5 集合库TreeDictionary和nuget和github有一个

bool TryPredecessor(K k, out KeyValuePair res) 如果存在 k 的前任，则返回 true，并且在这种情况下将前任绑定到 res；否则返回 false 并将 KeyValuePair 的默认值绑定到 res。k 的前身是排序字典中根据键比较器严格小于 k 的最大键的条目。如果 k 没有前置条目，则抛出 NoSuchItemException；也就是说，没有任何键小于 k。

和一个

bool TrySuccessor(K k, out KeyValuePair res) 如果有 k 的后继者并且在这种情况下将后继者绑定到 res，则返回 true；否则返回 false 并将 KeyValuePair 的默认值绑定到 res。k 的后继是排序字典中根据键比较器严格大于 k 的最小键的条目。如果 k 没有后继者，则抛出 NoSuchItemException；也就是说，字典中的任何条目都没有大于 k 的键。

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

于 2015-04-20T11:27:02.273 回答