問題タブ [interval-tree]

バイラルまたは制限的なライセンスなしで、効率的な C++ 間隔ツリーの実装 (ほとんどの場合、赤黒木に基づく) を見つけようとしています。クリーンで軽量なスタンドアロン実装へのポインタはありますか? 私が念頭に置いているユースケースでは、一連の間隔は最初からわかっており (100 万と言うでしょう)、特定の間隔と重なる間隔のリストをすばやく取得できるようにしたいと考えています。したがって、一度構築されたツリーは変更されません。迅速なクエリが必要なだけです。

間隔（または範囲）のリストがあるとしましょう（例：10-15、5-7、9-12 ..）。問題は、重複する範囲のサブセットを見つけることです。もちろん、これにはインターバルツリーを使用できます。

私が抱えている実際の問題は、複数の範囲があることです。例によって最もよく説明されています：

1. 10-15、5-7、9-12
2. 1-2、3-6、14-15
3. 3-5、9-15、10-15

上記の場合、第 2 範囲では (1) と (2) が重複し、第 3 範囲では (3) と (1)、(2) が重複しています。

基本的に、アイテムのリスト間の重複をすべて見つける必要があります。

たぶん、これを見つけるために 3 つの別々のインターバル ツリーを使用できます。これを行うより良い方法はありますか？

JavaでIntervalTreeまたはRangeTreeの実装が必要ですが、削除サポートが機能しているものを見つけるのに問題があります。

sun.jvm.hotspot.utilities.IntervalTreeに組み込みのものがありますが、RBTreeスーパークラスのdeleteNodeメソッドは次のように述べています。

ツリーからノードを削除しようとすると、例外がスローされます。

ノードの最大エンドポイントが正しく更新されませんでした

deletesun.jvm.hotspot.utilities.IntervalTreeのサブクラスに機能を適切に実装することはどれほど難しいでしょうか。または、これをすでに正しく実装している別の区間木実装はありますか？

現在、私はツリーを一掃し、削除があるたびに再入力しています。これは理想からはほど遠いです（注：RBTreeでDEBUGGING = falseを設定すると、処理が大幅に高速化されます）。

CLR の赤黒間隔ツリーに似た間隔ツリー アルゴリズムを探していますが、既定で間隔のマージをサポートしているため、間隔が重複することはありません。

つまり、2 つの間隔 [2,3] と [5,6] を含むツリーがあり、間隔 [4,4] を追加すると、結果は 1 つの間隔 [2,6] のみを含むツリーになります。

ありがとう

更新: 私が検討しているユース ケースは、推移閉包の計算です。間隔セットは、非常にコンパクトであることがわかっているため、後続セットを格納するために使用されます。しかし、間隔セットをリンクされたリストとして表すと、状況によっては間隔セットが非常に大きくなり、挿入ポイントを見つけるのに必要な時間がかかることがわかりました。したがって、インターバルツリーに興味があります。また、1 つのツリーを別のツリーとマージする (つまり、セット OR 操作) ことが非常に多い場合があります。両方のツリーが大きい場合は、各間隔の挿入を繰り返すよりも、両方のツリーの順序どおりのウォークを使用して新しいツリーを作成する方がよい場合があります。

ここで興味深い質問があります。N 個の間隔 ([開始、終了]) のセットが与えられた場合、間隔ツリーを使用して重複する間隔の最大数を見つけます。

StackOverflowに関する同様の質問で O(N) 解が提供されましたが、間隔を前処理して間隔ツリーにすることができれば、おそらく対数時間で解を見つけることができます。

実際、Cormen らによる「Introduction to Algorithms」の演習問題は、これが赤黒間隔ツリーを拡張することによって可能であることを示唆しています。これを行う方法はありますか？

ここでC++ のものを見つけることができましたが、純粋な C のものは見つかりませんでした。ポインタはありますか？

誰かがinterval treeC++での良い実装を知っていますか？

明らかに、テンプレート駆動型で、boostスタイルのようなものが優れています。

そして別の質問-誰かがテストした場合、std::vectorソートを使用した基本ベースの区間木実装は、実際には一般的な区間木（O（lg）操作を使用）を打ち負かすことができますか？

私はここ数日、無制限の次元をサポートするR-Treeの安定した実装を探していました（20程度で十分です）。私はこのhttp://sourceforge.net/projects/jsi/しか見つけませんでしたが、2次元しかサポートしていません。

別のオプションは、区間木の多次元実装です。

たぶん私は私の問題にRツリーまたはインターバルツリーを使用するという考えに完全に間違っているので、私は問題を簡単に述べます、あなたはこれについてのあなたの考えを私に送ることができます。

私が解決する必要のある問題は、ある種の最近傍探索です。アンテナと部屋のセットがあり、アンテナごとに整数の間隔があります。例：アンテナ1、最小-92、最大-85。実際、それは部屋->アンテナのセット->アンテナの間隔として表すことができます。アイデアは、各部屋がアンテナの次元を超えて、間隔によって各次元でRツリーのボックスにまたがるというものでした。

Nアンテナと各アンテナの値を使用してクエリを取得すると、情報を部屋のクエリポイントとして表し、そのポイントに「最も近い」部屋を取得できます。

あなたが問題のアイデアと私のアイデアを手に入れたことを願っています。

区間木C＃コレクションクラスを探しています。

間隔、理想的には2Dを追加できる必要があります。そうしないと、2つの標準的な1D間隔ツリーを組み合わせることができます。

また、特定の間隔と重なる間隔を見つける必要があります。

このintervaltree.codeplex.comを見つけましたが、

このリリースに関連するダウンロードはありません。

編集：

ここに続く：他のコードを使用したC＃

ここからC＃区間木コレクションクラスクラスをダウンロードしましたhttp://intervaltree.codeplex.com/SourceControl/list/changesets- >右側->ダウンロード。

ただし、Microsoft Visual C＃2010 Express（C＃XNAも実行）でプロジェクト全体を開くことはできません。

このバージョンのアプリケーションでは、ソリューションフォルダーはサポートされていません

また、クラスを自分の別のプロジェクトで個別に使用したいだけです。

3つの重要なファイルInterval.csをプロジェクトにコピーしようIntervalNode.csとしIntervalTree.csましたが、コンパイルエラーが発生しました

このファイルタイプを処理するインポーターはありません

また、3つのファイルの内容をコピーしてプロジェクトに貼り付け、それらを独自の名前空間にカプセル化しようとしました。また、多くのコードがありました。using Wintellect.PowerCollections;私はいくつかの使用法を少し再調整する必要がありましたが、おそらくそれが原因としてPowerCollections.dllおよび.pcbファイルを必要とするという問題に遭遇しました

タイプまたは名前空間の名前'Wintellect'が見つかりませんでした（usingディレクティブまたはアセンブリ参照がありませんか？）

続行する方法や、このクラスを機能させる方法についてまったく正しいことをしているのかどうかはわかりません。