多次元二分探索木

基本概念

多次元二分探索木（略してk-d木）は、マルチキーレコードを格納するためのデータ構造として定義されます。この構造は、統計およびデータ分析における多くの「幾何学的」問題を解決するために実装されました。

k-dツリー（k次元ツリーの略）は、k次元空間内のポイントを編成するための空間分割データ構造として定義されます。データ構造のk-dツリーは、多次元検索キーを含む検索（範囲検索や最近傍検索など）など、いくつかのアプリケーションに実装されます。 k-d木は、バイナリ空間分割ツリーの特殊なケースとして扱われます。

非公式の説明

k-dツリーは、すべてのリーフノードがk次元の点として扱われる二分木です。すべての非リーフノードは、空間を半空間と呼ばれる2つの部分に分割する分割超平面（中央値として使用）を暗黙的に生成するものとして想像できます。この超平面の左側のポイントは、そのノードの左側のサブツリーによって処理され、超平面の右側のポイントは、右側のサブツリーによって処理されます。次の方法で超平面の方向を選択できます。ツリー内のすべてのノードは、その次元の軸に垂直な超平面とともに、k次元の1つに関連付けられます。したがって、たとえば、特定の分割に対して「x」軸が選択された場合、ノードよりも「x」値が小さいサブツリー内のすべてのポイントが左側のサブツリーに表示され、「x」値が大きいすべてのポイントは次のようになります。右側のサブツリーにあります。このような場合、超平面は点のx値によって設定され、その法線は単位x軸を示します。一般的な方法は、ランダムに選択された固定数のポイントを並べ替え、それらのポイントの中央値を実装して分割平面として機能させることです。

n個のポイントのリストが与えられると、次のアルゴリズムは中央値の検索ソートを使用して、それらのポイントを含むバランスの取れたk-dツリーを構築します。

function KDtree (list of points PointList, int Depth) {
   // Choose axis based on Depth so that axis cycles through all valid values
   var int axis := Depth mod k;
   // Sort point list and select median as pivot element
   choose median by axis from PointList;
   // Node is created as node1 and construct subtree
   node1.location := median;
   node1.leftChild := KDtree(points in PointList before median, Depth+1);
   node1.rightChild := KDtree(points in PointList after median, Depth+1);
   return node1;
}