区間木

与えられたセット${\displaystyle n}$数直線上の区間を扱う場合、他の区間や点と重なるすべての区間を効率的に取得できるように、データ構造を構築する必要があります。

まず、すべての区間の全範囲を取り、${\displaystyle x_{\textrm {center}}}$（実際には、 ${\displaystyle x_{\textrm {center}}}$木のバランスを保つために選択する必要があります。これにより、3 つの間隔のセットが得られます。 ${\displaystyle x_{\textrm {center}}}$と呼ばれる${\displaystyle S_{\textrm {left}}}$完全に右派の${\displaystyle x_{\textrm {center}}}$と呼ばれる ${\displaystyle S_{\textrm {right}}}$重複するもの${\displaystyle x_{\textrm {center}}}$と呼ばれる${\displaystyle S_{\textrm {center}}}$。

間隔 ${\displaystyle S_{\textrm {left}}}$そして ${\displaystyle S_{\textrm {right}}}$区間がなくなるまで、同じ方法で再帰的に分割されます。

間隔${\displaystyle S_{\textrm {center}}}$中心点と重なる区間は、区間ツリーのノードにリンクされた別のデータ構造に格納されます。このデータ構造は2つのリストで構成され、1つは開始点順に並べられたすべての区間、もう1つは終了点順に並べられたすべての区間を含みます。

結果として、各ノードに以下の情報を格納する二分木が得られます。

• 中心点
• 中心点の左側にあるすべての区間を含む別のノードへのポインタ
• 中心点の右側にあるすべての区間を含む別のノードへのポインタ
• 中心点と重なるすべての区間を、開始点順に並べたもの
• 中心点と重なるすべての区間を終点順に並べたもの

区間木を用いると、任意の入力と重なるすべての範囲を迅速に計算できる。

確かに

課題は、与えられた点と重なるツリー内のすべての区間を見つけることです。${\displaystyle x}$ツリーは、従来の二分木を走査するのと同様の再帰アルゴリズムで走査されますが、各ノードの「中心」点と重なる区間を検索するための追加ロジックが組み込まれています。

各ツリーノードについて、${\displaystyle x}$と比較される ${\displaystyle x_{\textrm {center}}}$上記のノード構築で使用された中間点。${\displaystyle x}$より小さい ${\displaystyle x_{\textrm {center}}}$、最も左の区間のセット、 ${\displaystyle S_{\textrm {left}}}$、考慮されます。${\displaystyle x}$より大きい ${\displaystyle x_{\textrm {center}}}$最も右側の区間のセット、 ${\displaystyle S_{\textrm {right}}}$考慮される。

ツリーがルートからリーフへとたどられるにつれて各ノードが処理されるにつれて、その範囲は ${\displaystyle S_{\textrm {center}}}$処理されます。${\displaystyle x}$より小さい ${\displaystyle x_{\textrm {center}}}$、すべての区間 ${\displaystyle S_{\textrm {center}}}$終了しなければならない${\displaystyle x}$あるいは、それらは重複することもできない。 ${\displaystyle x_{\textrm {center}}}$したがって、次の区間を見つけるだけでよい。${\displaystyle S_{\textrm {center}}}$始まる前に${\displaystyle x}$. リスト${\displaystyle S_{\textrm {center}}}$既に構築されているものを参照できます。このシナリオでは区間の開始点のみが関係するため、リストを開始点でソートできます。最も近い数値が以下であれば${\displaystyle x}$このリストに見つかった場合、リストの先頭から見つかったポイントまでのすべての範囲が重なります${\displaystyle x}$なぜなら、それらは前に始まるから${\displaystyle x}$そして、その後終了する${\displaystyle x}$（重複しているため）${\displaystyle x_{\textrm {center}}}$これはより大きい${\displaystyle x}$したがって、開始点の値がを超えるまでリスト内の区間を列挙することができます。${\displaystyle x}$。

同様に、${\displaystyle x}$より大きい ${\displaystyle x_{\textrm {center}}}$、すべての区間 ${\displaystyle S_{\textrm {center}}}$開始前に開始する必要があります${\displaystyle x}$、したがって、${\displaystyle x}$区間の末尾でソートされたリストを使用することで見つけることができます。

もし${\displaystyle x}$完全に一致する${\displaystyle x_{\textrm {center}}}$、すべての区間${\displaystyle S_{\textrm {center}}}$追加処理なしで結果に追加でき、ツリー走査を停止できます。

区間木データ構造は、より高次元に一般化することができる。${\displaystyle N}$クエリと構築時間が同一で、${\displaystyle O(n\log n)}$空間。

まず、レンジツリー${\displaystyle N}$クエリ領域内に開始点と終了点を持つすべての区間を効率的に取得できる次元が構築されています。${\displaystyle R}$対応する範囲が見つかったら、残っているのは、ある次元で領域を囲む範囲だけです。これらの重なりを見つけるには、 ${\displaystyle N}$区間ツリーが作成され、1 つの軸が交差します${\displaystyle R}$それぞれについてクエリが実行されます。たとえば、2 次元では、正方形の底辺がクエリされます。 ${\displaystyle R}$（または交差する他の水平線）${\displaystyle R}$）は、水平軸用に構築された区間ツリーに対してクエリされます。同様に、左側の（または交差する他の垂直線）${\displaystyle R}$）は、垂直軸上に構築された区間木に対してクエリされます。

各区間木には、より高次元のための追加も必要です。木をたどる各ノードでは、${\displaystyle x}$と比較される ${\displaystyle S_{\textrm {center}}}$重なりを見つける。1 次元の場合に使用された 2 つのソートされた点のリストの代わりに、範囲ツリーが構築される。これにより、すべての点を効率的に取得できる。 ${\displaystyle S_{\textrm {center}}}$重複領域${\displaystyle R}$。

ツリーからある区間を削除した後、その区間を含むノードに他の区間がなくなった場合、そのノードはツリーから削除される可能性があります。これは、通常の二分木の削除操作よりも複雑です。

区間は、ツリー内の複数のノードの中心点と重なる場合があります。各ノードは、自身と重なる区間を格納しており、左サブツリーでは中心点の左側にあるすべての区間が、右サブツリーでは同様に格納されるため、各区間は、その中心点が重なるノードの集合の中で、ルートに最も近いノードに格納されることになります。

二分木における通常の削除操作（削除対象のノードが2つの子を持つ場合）では、葉ノードからさらに離れたノードを削除対象のノードの位置（通常は右部分木の最も左の子、または左部分木の最も右の子）まで昇格させる。

この昇格の結果、昇格したノードより上位にあったノードの一部が、昇格したノードの子孫になります。これらのノードの中から、昇格したノードと重なる区間を探し出し、それらの区間を昇格したノードに移動させる必要があります。その結果、新たな空のノードが生じる可能性があり、それらは同じアルゴリズムに従って削除しなければなりません。

削除に影響を与えるのと同じ問題が回転操作にも影響します。回転操作では、ノードが可能な限りルートに近い場所に格納されるという不変条件を維持する必要があります。

ツリーが不要な走査を避けることで、パフォーマンスが向上する場合があります。これは、既に存在する区間を追加したり、存在しない区間を削除したりする際に発生する可能性があります。

区間に対しては、まず下限値で、次に上限値で順序付けすることにより、全順序を定義できます。次に、メンバーシップチェックを実行できます。${\displaystyle O(\log n)}$時間、対${\displaystyle O(k+\log n)}$重複を見つけるのに必要な時間${\displaystyle k}$区間は挿入または削除する区間と重複します。このソリューションの利点は、追加の構造を必要としないことです。変更は厳密にはアルゴリズム的なものです。欠点は、メンバーシップクエリに時間がかかることです。${\displaystyle O(\log n)}$時間。

あるいは、${\displaystyle O(n)}$メモリ使用量と期待定数時間でのメンバーシップクエリは、区間ツリーと同期して更新されるハッシュテーブルを使用することで実装できます。区間を値ではなく参照で格納する場合、必ずしも総メモリ使用量が2倍になるとは限りません。

各ノードのキーは区間そのものであり、したがってノードはまず値の小さい順に、最後に値が大きい順に並べられ、各ノードの値は区間の終点となる。

public void add ( Interval i ) { put ( i , i.getEnd ( )) ; }

区間を検索するには、キー（n.getKey()）と最大値（n.getValue()）を使用してツリーをたどり、クエリと重複しないブランチを除外します。最も単純なケースは、ポイントクエリです。

// ノード「n」から始めて、「p」を含むすべての区間を検索し、一致する区間をリスト「result」に追加します。public void search ( IntervalNode n , Point p , List < Interval > result ) { // 存在しないノードは検索しませんif ( n == null ) return ;// p がこのノードおよびすべての子ノード内の任意の区間の右端の点よりも右にある場合、// 一致するものはありません。if ( p . compareTo ( n . getValue ()) > 0 ) return ;// 左の子要素を検索search ( n . getLeft (), p , result );// このノードをチェックします。もし (n.getKey ( ) . contains ( p ) )ならば、result.add ( n.getKey ( ) ) ;// p がこの区間の開始位置の左側にある場合、// 右側のどの子要素にも含まれません。if ( p . compareTo ( n . getKey (). getStart ()) < 0 ) return ;// それ以外の場合は、右の子要素を検索するsearch (n.getRight ( ) , p , result ) ; }

どこ

a.compareTo(b)a < b の場合、負の値を返します。

a.compareTo(b)a = b の場合、ゼロを返します。

a.compareTo(b)a > b の場合、正の値を返します。

区間を検索するコードは、途中のチェックを除いて同様です。

// このノードをチェックしますif ( n . getKey (). overlapsWith ( i )) result . add ( n . getKey ());

overlapsWith()は次のように定義されます。

public boolean overlapsWith ( Interval other ) { return start.compareTo ( other.getEnd ( ) ) < = 0 && end.compareTo ( other.getStart ( ) ) > = 0 ; }​​

拡張木は、木の各レベルで次元を順に処理することで、より高次元に拡張できます。例えば、2次元の場合、木の奇数レベルにはx座標の範囲が、偶数レベルにはy座標の範囲が含まれる可能性があります。このアプローチは、データ構造を拡張二分木から拡張kd木に効果的に変換するため、挿入と削除のバランス調整アルゴリズムを著しく複雑化させます。

より簡単な解決策は、ネストされた区間木を使用することです。まず、 y座標の範囲を使用して木を作成します。次に、木の各ノードについて、y範囲がそのノードのy範囲と同じであるすべての要素に対して、x範囲に基づいて別の区間木を追加します。

このソリューションの利点は、同じコードベースを使用して任意の次元数に拡張できる点です。

最初は、入れ子構造のツリーによる追加コストが高額に思えるかもしれませんが、実際にはそうではありません。前述の入れ子構造ではない解法と同様に、x座標ごとに1つのノードが必要となるため、どちらの解法でもノード数は同じになります。唯一の追加オーバーヘッドは、垂直方向の区間ごとに1つ存在する入れ子構造のオーバーヘッドです。この構造は通常、ルートノードへのポインタと、場合によってはノード数およびツリーの深さのみで構成されるため、サイズはごくわずかです。

2つの区間の開始値と終了値のみを使用する${\displaystyle \left(a_{i},b_{i}\right)}$、 のために${\displaystyle i=0,1}$オーバーラップテストは次のように実行できます。

${\displaystyle a_{0}<b_{1}}$そして${\displaystyle a_{1}<b_{0}}$

これは、和と差を用いて簡略化できます。

$s_i=a_i+b_i$

$d_i=b_i-a_i$

これにより、重複テストは以下のように簡略化されます。

$\displaystyle \left|s_{1}-s_{0}\right|<d_{0}+d_{1}}$

ツリーに新しい区間を追加する方法は、中央値をキーとして使用する二分探索木の場合と同じです。$d_i$ノードに関連付けられたバイナリヒープにデータを格納し、上位のすべてのノードに関連付けられた最小値と最大値を更新します。

使用しましょう${\displaystyle a_{q},b_{q},m_{q},d_{q}}$クエリ間隔の場合、${\displaystyle M_{n}}$ノードのキーの場合（${\displaystyle m_{i}}$（間隔の）

ルートノードから始めて、各ノードにおいて、まず、クエリ区間がノードの最小値と最大値を使用してノードのサブツリーと重複する可能性があるかどうかを確認します（重複しない場合は、このノードの処理は続行しません）。

次に計算します${\displaystyle \min \left\{d_{i}\right\}}$このノード内の区間（子ノードではない）がクエリ区間と重なるように（${\displaystyle m_{i}=M_{n}}$):

${\displaystyle \min \left\{d_{i}\right\}=\left|m_{q}-M_{n}\right|-d_{q}}$

そして、そのバイナリヒープに対してクエリを実行します。$d_i$より大きい${\displaystyle \min \left\{d_{i}\right\}}$

次に、ノードの左の子と右の子の両方を同様に処理します。

最悪の場合、二分探索木のすべてのノードをスキャンする必要がありますが、二分ヒープクエリが最適であるため、これは許容範囲内です（2次元の問題は両方の次元で最適になることはできません）。

このアルゴリズムは、検索操作において従来の区間木（拡張木）よりも高速であることが期待されます。要素の追加は実際には若干遅くなりますが、成長の順序は同じです。