スイープ ライン (SL) に次のプロパティを持つデータ構造を必要とするBentley-Ottman アルゴリズムを実装しています。
- のソートされたコレクションを
T維持するTIComparable<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)挿入/削除があります。独自のバランスの取れたツリーを実装する必要はありますか?