問題タブ [range-tree]

現在、2D 範囲ツリーを実装しています。Node クラスのもっともらしいモデル (Java で) を考え出すのに苦労しています。

ツリー内のノードは、次のいずれかを持つことができます: 中間値、右および左の子ポインター、サブツリー、データ ポインター、および/または前および次のポインター。

ノードを 3 つの個別の論理ピースに分割しました

• a) midRange 値のみを持つノード - すべてのノードに midRange があります
• b) 左点、右点、およびサブツリー ポイントを持つノード。これは非リーフ ノードを表します。
• c) next、prev、および data ポインターを使用しない。これは葉ノードを表します。

Composite パターンと Decorator パターンを適用しようとしましたが、役に立ちませんでした。私は作ってみました：

1. 可能なすべてのゲッター/セッターを備えたノード インターフェイス、つまり、getMidRange、getLeft、getRight、setLeft、setRight など...
2. Node2D と LinkedNode (リーフ ノード) の 2 つのクラスでインターフェイスを実装します。Node2D は、次と前へのリンクを保持すること以外はすべて行いました。一方、LinkedNode は次と前へのリンクのみを保持していました。

それはそのように機能しますが、これを一連のクラスとしてモデル化するより良い方法があるかどうか、私はさまよっていましたか?

編集:範囲ツリー(短い情報): 範囲ツリーでは、すべてのデータがリーフ ノードに格納され、ツリーは常にバランスが取れています。さらに、すべての葉は同じ高さです。また、リーフはソートされ、二重リンク リストによってリンクされます。最後になりましたが、葉ではない各ノードにはサブツリーがあります。これは範囲ツリーでもありますが、葉は次の属性でソートされています (元のツリーがxでソートされていた場合はyとします)。

Ruby での範囲ツリーまたはセグメント ツリーの実装を探しています。利用可能なサンプルまたは宝石が見つかりませんでした。

誰もサンプルコードを持っていますか?

ありがとう、

私は 3D 空間でオブジェクトを検索する必要があるこのプロジェクトに取り組んでおり、効率が大きな懸念事項です。Range Tree は私がやろうとしていることに最適だと思います。Interval Tree も機能しますが、私はそうではありませんツリーから何かを削除するつもりです。3D 空間にすべてのオブジェクトを追加したら、その構造を使用して検索を行います。

構造体を使用する方法は次のとおりです。

オブジェクト（〜10,000オブジェクト）の配列（ queryArrと呼びましょう）があるとしましょう各オブジェクトには3つのパラメーター（x、y、z）がありますオブジェクト（> 5,000,000オブジェクト）の別の非常に大きな配列（ totalArrと呼びましょう）があります）。

ここでやろうとしているのは、queryArrの要素を指定して、最も類似した (またはtotalArrの同じ要素) を見つけることです。場合によっては、 totalArrに同じパラメーターを持つオブジェクトが存在しますが、ほとんどの場合、存在しません。同じパラメータを持つオブジェクトになります。

(x+10,y+10,z+10)したがって、との間のすべての値を検索します(x-10,y-10,z-10)。結果が得られない場合は、x、y、z に 2 を掛けて、何らかの結果が得られるまで再試行します。

これを行う最も簡単な方法は単純な検索方法です。これは複雑です O(N*M) (N = size of queryArr, M = sie of totalArr)が、この方法は信じられないほど遅くて愚かです。

レンジ ツリーが最適な方法だと思いますが、自分で実装したことがなく、レンジ ツリーが 2 より大きい次元でどのように機能するかよくわかりません。レンジ ツリーの適切な実装を知っている人はいますか? ソースコードがあれば、それらが実際にどのように機能するかを理解できると思います。

ところで、このタスクにはレンジ ツリーよりも優れた構造があると思われる場合は、提案をお待ちしております。(kd-Trees と Interval trees は既に検討済みです)

ありがとう、

しばらくの間、範囲ツリーを理解しようとしてきましたが、まだ理解できません。

2D RMQを解決するためにそれを使用したいので、誰かが実装でそれを説明してもらえますか?複雑さは、2D セグメント ツリーのように n^2 未満にすることができます。

これについてはよくわかりませんが、マージソートのようなものなので、ベクターを使用するとメモリがn ^ 2未満になるというのは本当ですか

ありがとう ：）

こんにちは、RMQ 用に 2D レンジ ツリーを実装しようとしています。これが私のコードです。十分に効率的ではないと思います。最適化のためにできることはありますか。

ls には、すべてのノードでソートされた y のリストが含まれます

rt にはセグメント ツリーが含まれます

p.fi.fi には x 座標が含まれます

p.fi.se には y 座標が含まれます

p.seにはポイントのIDが含まれています

loc には、各 ID の x ノードと y ノードが含まれます

範囲ツリーの最初の実装なので、コードがめちゃくちゃだったらごめんなさい

私の現在の実装は約4秒間実行されますが、3秒未満で実行する必要があります。これが私の完全な 実装です

ありがとう ：）

7次元空間に約10 ^ 4ポイントがあります。特定のアプリケーションでは、特定の範囲内にあるすべてのポイントを見つけるために、この入力に対して ~10^6 の範囲クエリを作成する必要があります。このアプリケーションでは、すべてのクエリが同じ範囲サイズを使用しています。この問題に適したデータ構造は何ですか?

kd-tree が適しているように見えますが、7 次元で出力サイズが小さい場合、クエリの時間の複雑さはほぼ直線的です。もう 1 つの解決策はレンジ ツリーですが、このアプリケーションでは少数の入力に対して構成するには複雑すぎるようです。また、範囲が一定のサイズであるという事実を有利に利用しているこれらの構造は見当たりません。たとえば、これが 1D の問題である場合、クエリはすべて、たとえばサイズ 10 の範囲内にあるポイントを、数直線に沿ったさまざまな場所で求めることになります。

宿題

O(logn*ログイン）。

kd-tree と range tree の 2 つの可能性を考えています。kd ツリーは、O(logn + k) の範囲内の要素を見つけることができるため、これに適しています (報告する必要がある k 要素の場合)。しかし、要素を報告する必要はありません。範囲内にある要素の数を計算する必要があるだけです。

範囲ツリーはその中で機能する可能性があります。各ノードに、それ自体よりも少ない数を保持するプロパティを設定できます。このようにして、O(logn) 回で特定の値よりも小さい要素の数を特定できます (2 つの境界に移動し、互いに小さいノードの数の差を見つけることによって)。ただし、これは (x,y) 次元の両方を持つデータ セットでは機能しないと思います。

私は正しい軌道に乗っていますか？

近隣探索問題を解決する必要があります。つまり、特定の要素ごとに、一定の距離内にあるすべての近隣要素を見つけます。

私はデータ構造を学んだばかりでrange tree、この問題を O(N*(log(N)^(d-1))) の複雑さで解決できるようです。ここで、d は薄暗いスペースです。

については何も知りませんが、ウィキペディアR-treeからこれを見ただけです：

R ツリーの一般的な実世界での使用法は .... で、「現在地から 2 km 以内にあるすべての美術館を検索する」などのクエリに対する回答をすばやく見つけることができます。

これはまさに私が解決したい問題のようです。

では、このデータ構造を学習して使用する必要がありますか?</p>

範囲検索用のデータ構造を探しています。範囲ツリーは適切な時間の複雑さを提供すると思います (ただし、いくつかのストレージ要件があります)。

ただし、範囲ツリーよりも、 KD ツリーなどの他のデータ構造の方が議論され、推奨されているように思えます。これは本当ですか？もしそうなら、なぜですか？