レンジツリー

レンジツリー
タイプ	木
発明された	1979
発明者	ジョン・ルイス・ベントレー
ビッグ O 記法による時間計算量 手術 平均 最悪の場合 検索 ${\displaystyle O(\log^{d}n+k)}$ ${\displaystyle O(\log^{d}n+k)}$ 空間の複雑さ 空間 ${\displaystyle O(n\log ^{d-1}n)}$ ${\displaystyle O(n\log ^{d-1}n)}$

コンピュータサイエンスにおいて、範囲木は、ポイントのリストを保持する順序付きツリー データ構造です。範囲木を使用すると、特定の範囲内のすべてのポイントを効率的に報告することができ、通常は2次元以上で使用されます。範囲木は、1979年にJon Louis Bentleyによって導入されました。 ^{[1]同様のデータ構造は、Lueker、 [2]} LeeとWong、^[3] Willardによって独立に発見されました。 ^{[4]範囲木は、} k -d木 に代わるものです。k-d木と比較して、範囲木は（Big O表記で）のクエリ時間が短くなりますが、のストレージは悪くなります。ここで、nはツリーに格納されるポイントの数、dは各ポイントの次元、kは特定のクエリによって報告されるポイントの数です。 ${\displaystyle O(\log ^{d}n+k)}$${\displaystyle O(n\log ^{d-1}n)}$

1990年にバーナード・チャゼルはこれを改良し、時間と空間の複雑さを問いました。^{[5] [6]}${\displaystyle O(\log ^{d-1}n+k)}$${\displaystyle O\left(n\left({\frac {\log n}{\log \log n}}\right)^{d-1}\right)}$

1 次元の点の集合に関する範囲木は、それらの点に関するバランスのとれた二分探索木です。木に格納されている点は木の葉に格納され、各内部ノードにはその左のサブツリーの最大値を格納します。d次元の点の集合に関する範囲木は、再帰的に定義された多レベル二分探索木です。データ構造の各レベルは、d次元のいずれかの二分探索木です。最初のレベルは、 d座標の最初の座標に関する二分探索木です。この木の各頂点vには、 vのサブツリーに格納されている点の最後の ( d −1) 座標に関する ( d −1) 次元の範囲木である関連構造が含まれます。

n個の点の集合上の 1 次元の範囲木は二分探索木であり、時間内に構築できます。高次元の範囲木は、点の最初の座標上にバランスのとれた二分探索木を構築し、次にこの木の各頂点vに対して、 vのサブツリーに含まれる点上に ( d −1) 次元の範囲木を構築することによって再帰的に構築されます。この方法で範囲木を構築するには時間がかかります。 ${\displaystyle O(n\log n)}$${\displaystyle O(n\log ^{d}n)}$

この構築時間は、2次元範囲木では まで改善できます。^[7] S をn 個の2次元点の集合と します。 Sに点が1つしか含まれていない場合は、その点を含む葉を返します。それ以外の場合は、 Sの関連構造、つまりS内の点のy座標上の1次元範囲木を構築します。x _{m を点の}x座標の中央値とします。S _{L を}x座標がx _m以下の点の集合とし、S _{R を}x座標がx _mより大きい点の集合とします。S _L上の2次元範囲木v _LとS _R上の2次元範囲木v _Rを再帰的に構築します。左の子がv _Lで右の子がv _Rである頂点v を作成します。アルゴリズムの開始時に点をy座標でソートし、点をx座標で分割するときにこの順序を維持すれば、各サブツリーの関連構造を線形時間で構築できます。これにより、2 次元の範囲ツリーの構築時間が に短縮され、 d次元の範囲ツリーの構築時間も に短縮されます。 ${\displaystyle O(n\log n)}$${\displaystyle O(n\log n)}$${\displaystyle O(n\log ^{d-1}n)}$

範囲ツリーの範囲クエリは、指定された間隔内にあるポイントのセットを報告します。間隔 [ x ₁、x ₂ ] 内にあるポイントを報告するには、まずx ₁とx ₂を検索します。ツリー内のある頂点で、x ₁とx ₂への検索パスが分岐します。v _{split を、}これら 2 つの検索パスが共通する最後の頂点とします。v _splitからx ₁への検索パスにあるすべての頂点vについて、 vに格納されている値がx ₁より大きい場合は、 vの右サブツリーにあるすべてのポイントを報告します。vがリーフの場合は、 v がクエリ間隔内にある場合に、vに格納されている値を報告します。同様に、 v _splitからx ₂への検索パスに沿ってx ₂未満の値を持つ頂点の左サブツリーに格納されているすべてのポイントを報告し、このパスのリーフがクエリ間隔内にある場合はそれを報告します。

範囲ツリーはバランスのとれた二分木なので、 x ₁とx ₂への検索パスの長さは です。頂点のサブツリーに格納されているすべてのポイントを報告することは、任意のツリートラバーサル アルゴリズムを使用して線形時間で実行できます。したがって、範囲クエリの実行時間は です。ここで、k はクエリ間隔内のポイントの数です。 ${\displaystyle O(\log n)}$${\displaystyle O(\log n+k)}$

d次元の範囲クエリも同様です。検索パスのサブツリーに格納されているすべてのポイントを報告する代わりに、各サブツリーの関連構造に対して ( d −1) 次元の範囲クエリを実行します。最終的には、1 次元の範囲クエリが実行され、正しいポイントが報告されます。d次元クエリは( d −1) 次元の範囲クエリで構成されているため、 d次元の範囲クエリを実行するために必要な時間は になります。ここで、kはクエリ間隔内のポイントの数です。これは、分数カスケーディングの変形を使用してに短縮できます。^{[2] [4] [7]}${\displaystyle O(\log n)}$${\displaystyle O(\log ^{d}n+k)}$${\displaystyle O(\log ^{d-1}n+k)}$

• k -d ツリー
• セグメントツリー
• 範囲検索

• 計算幾何学アルゴリズム ライブラリCGALの範囲ツリーとセグメント ツリー。
• 講義 8: Range Trees、Marc van Kreveld。アーカイブはこちら。
• 並列拡張マップライブラリPAMを使用した範囲ツリー。
• 2D 範囲ツリー可視化、Zhou Kaixuan。