c# - C# での赤黒ツリーの実装

Question

次の機能を備えた、C# での赤黒ツリーの実装を探しています。

• O(log n) での検索、挿入、削除。
• メンバー型はジェネリックである必要があります。
• Comparer(T)でのサポート、その中のT異なるフィールドによるソート。
• ツリーでの検索は特定のフィールドを使用する必要があるため、 は受け入れませんがT、ソートするフィールド タイプは受け入れます。
• 検索は正確な値だけであってはなりません。下位/上位の検索をサポートする必要があります。

ありがとうございました。

Answer 1

これはまさに PowerCollections の OrderedDictionary です。これは、開始キー/終了キーを設定し、その範囲内のすべての値をスキャンする機能が追加されていることを除けば、SortedDictionary (ジェネリックを含む赤黒ツリー) とほとんど同じです。

SortedDicionary は、コレクションの先頭から開始する GetEnumerator() 関数の公開のみを許可し、MoveNext() 呼び出しのみを許可するため、LINQ を使用しても魔法は何も起こりません: 最初から開始し、すべての単一で式を実行します。 LINQ 式に一致するものが見つかるまで、ノードを順番に検索します。

OrderedDictionary には、特定のキーまたはその前で列挙子を取得し、O(log n) でルックアップを行う関数があります。

ただし、注意事項: PowerCollections OrderedDictionary の列挙子は「yield」を使用して実装され、メモリ使用量と列挙のパフォーマンスは少なくとも O(n^2) です...実装を自分で変更して、従来の列挙子を実装することができますそして、これらの問題は両方ともなくなります。時間があれば、そのパッチを Codeplex に提出します。