多次元検索構造としてのBSPツリー

空間検索構造は、人の名前のリストなどの幾何学的データとは対照的に、シンボリックデータの大規模なセットを迅速に処理する問題を解決するために60年代と70年代にコンピュータサイエンスで発明されたものと同じアイデアに基づいています。最初に名前のリストをアルファベット順に並べ替え、並べ替えたリストを配列に格納することで、n / 2ではなく、バイナリ検索アルゴリズムを使用して、log2n操作で新しい名前がすでにリストにあるかどうかを計算できることが発明されました。順次検索の助けを借りて必要とされる予想される操作。これは、名前のリストに存在する構造（アルファベット順）を抽出し、後続の操作（名前の検索）でその構造を利用して計算を減らす良い例です。

ただし、ソートされたリストを維持しながら名前の追加と削除を許可したい場合は、動的なデータ構造、つまりポインタを実装するものが必要です。このようなデータ構造の最も一般的な例の1つは、二分探索木に他なりません。

二分探索木の場合、実数直線上にあるA ={1、2、5、6、7、9}などの整数のセットを表すために実装されています。数値/ポイントがすでにツリーにあるかどうかを計算するには、ポイントをツリーに挿入し、ポイントで構成されるネストされた間隔のシーケンスに対応するパスをたどることができます。バランスの取れたツリーの場合、このプロセスはO（log n）ステップしか消費しません。実際、バイナリ検索を実行しましたが、配列ではなくツリーを実装しています。これで、検索が進む順序を決定するため、ツリー自体が検索アルゴリズムの一部をエンコードできるようになりました。

これでパーティショニングツリーに戻ります。これらは、2分探索木の一般化として1を超える次元、つまり多次元（1Dでは本質的に同じ）に扱われます。実際、パーティショニングツリーの構築は、クイックソートの幾何学的バージョンとして想像することができます。

変更（削除と挿入）は、マージソートでソートされたリストをマージするのと同様に、ツリーをマージすることによって実現されます。

ただし、ポイントは1を超える次元のスペースを分割しないため、細分割するポイントではなく超平面を実装する必要があります。

超平面は、寸法に関係なく、常に領域を2つの半空間に分割または分割します。