Hanson と Chaabouni によるInterval Binary Search Treeの C# 実装に取り組んでいます。簡単に言えば、これは動的間隔コレクションのデータ構造であり、ポイントと重なる間隔をすばやく見つけることができます。データ構造は、AVL バランシング スキームを使用した拡張二分探索木 (BST) です。
ツリーの各ノードには、間隔の 3 つのセットが含まれています。回転を行うとき、不変条件を維持するために多くの集合操作を行う必要があります。セット内の間隔の反復、セットの加算と減算、およびセットの交差のサポートが必要です。コレクションに重複した間隔 (同じエンドポイントを持つが、同じオブジェクトではない間隔) が含まれている場合、それらは同じセットに含まれます。
これらの一連の操作をできるだけ速く実行できるようにする必要があります。これが私たちの制限要因です。これらの操作を効率的にサポートするデータ構造はありますか?
ボーナス情報:
- 間隔は、下限エンドポイントと上限エンドポイントで構成されます。彼らについて私たちが知っているのはそれだけです。
- これらのエンドポイントをハッシュすることはできますが、同じエンドポイントを持つ重複した間隔は当然同じハッシュコードになります。
- 間隔は、参照の等価性で区別されます。
- エンドポイントを並べ替えることができますが、同じエンドポイントを持つ重複した間隔は当然同じ並べ替え順序になります。
- ハッシュまたはソートに使用できる他の情報はありません。