"k"d木（）は、"k"次元のユークリッド空間にある点を分類する空間分割データ構造である。"k"d木は、多次元探索鍵を使った探索（例えば、範囲探索や最近傍探索）などの用途に使われるデータ構造である。"k"d木はBSP木の特殊ケースである。"k"d木は、座標軸の1つに垂直な平面だけを使って分割を行う。BSP木では分割平面の角度は任意である。さらに一般的には、"k"d木の根ノードから葉ノードまでの各ノードには1つの点が格納される。この点もBSP木とは異なり、BSP木では葉ノードのみが点（または他の幾何学的プリミティブ）を含む。つまり、"k"d木の各分割平面は必ず1つの点を通る。葉ノードのみがデータを格納する派生データ構造を"k"dトライと呼ぶ。また、特記すべき"k"d木の別の定義として、各分割平面が1つの点を通るよう決定されるものの、点を葉ノードでのみ記憶するという定義もある。軸に対応した分割平面の選択方法は様々なものがあり、"k"d木の構築方法も様々である。典型的な"k"d木の構築方法は以下のようになる。この方法では平衡"k"d木が得られ、各葉ノードと根との距離は等しくなる。しかし平衡木があらゆる応用において最適とは限らない。また、常に中央値となる点を選択することが求められているわけではない。中央値を気にしない場合、単に平衡木となることが保証されないだけである。中央値を選択するアルゴリズムやソートをしない場合のヒューリスティックとしては、固定個の点を無作為に選択し、それらの中の中央値を選んで分割するという方式がある。実用上はこの技法で十分平衡的な木が得られる。"n"個の点のリストを与えられたとき、以下のアルゴリズムで平衡"k"d木を構築できる。中央値より後ろ（after）の点には、中央値以上の座標値の点を含ませるのが一般的である。別の手法として、他の次元で点を比較する「スーパーキー(superkey)」関数を定義する方法もある。他にも、中央値に等しい点を両側に属させることもありうる。このアルゴリズムをPythonで実装すると次のようになる。このアルゴリズムは任意のノードについて不変条件を生成し、左の部分木にある全ノードは分割平面の一方の側にあり、右の部分木にある全ノードは同じ分割平面のもう一方の側にある。分割平面上にある点はどちらの側にも出現する可能性がある。あるノードの分割平面はそのノードに対応した点を通る（上記コードでは "node.location" で表されている）。"k"d木への点の追加は、他の木構造への要素の追加と同じように行える。まず、木の走査を根から開始し、追加しようとしている点が対応する座標値に対して右側なのか左側によって右または左の子ノードへと移っていく。葉ノードに到達したら、同様にそのノードに対応する点の座標値と比較して右または左に子ノードを追加する。"k"d木から1つの点を削除する場合、不変量が維持されるようにしなければならない。最も簡単な方法は、削除したい点に対応するノードから下の全ノードについて、対応する全ての点について"k"d木を再構築することである。ノードの軸およびピボット値を保持する必要がある。"k"d木の平衡化は注意を要する。"k"d木は多次元に渡ってソートされているため、一般的な木の回転 (tree rotation) を行って平衡化すると、不変量が保持されなくなる。"k"d木に含まれない点が与えられ、その点に最も近い"k"d木上の点を探す問題を考える（最近傍探索）。この場合、単純なテストで木の大部分を捨てられることを利用する。この場合、木構造を深さ優先探索で走査し、各段階で最短距離の近似計算を行う。アルゴリズム上より近傍の点がないと判断されたとき、最近傍が決定され、終了する。まず、最短距離を無限としておいて、根ノードを調べる。次に、与えられた点を含む右または左の部分領域（それぞれ超矩形になっている。3次元の場合は直方体）を探す。これを繰り返していって、与えられた点を含む最小の領域（葉ノード）を求める。次に上方向に再帰的に、親ノードのもう一方の領域がより近い点を持っていないかを調べていく。これは、与えられた点を中心として半径が現在の最近傍の点までの距離となる超球（3次元なら単なる球）と各領域の超矩形とが重なるかどうかを調べることでなされる。まだ調べていない矩形がこの球と重ならないなら、その矩形がより近い近傍点を含むことはない。これを全ての領域が捨てられるか探索されるまで繰り返す。そして、最終的に残った点が最近傍となる。さらにこのアルゴリズムは、単に最近傍を求めるだけでなく、最近傍の距離の二乗も求められる。このアルゴリズムの時間計算量は O(logN) である。このアルゴリズムは簡単な修正で拡張する方法がいくつか存在する。近似最近傍探索は、単に木構造上で調べる点の個数の上限を決めておくか、探索にかかる時間を決めておいて割り込むことで実現される（後者はハードウェアによる実装にふさわしい）。木構造にすでに含まれている座標の点の最近傍を求める場合、常に距離が0の点が存在するはずであり、近似によって探索を打ち切るとそれを求めることができないという問題がある。近似最近傍探索は劇的に計算時間を抑えられるため、ロボット工学などのリアルタイム性が要求される場合によく使われる。"k"d木は高次元空間での最近傍探索には適さない。次元を "D" としたとき、点の個数 "N" は "N » 2" となっているのが望ましい。そうでないと、高次元データを"k"d木で表すと、最近傍探索でほとんどの点を調べることになり、力まかせ探索とあまり差がない。高次元データでの最近傍探索問題はNP困難問題と似ていると考えられている。そのため近似最近傍探索の手法が使われることが多い。"k"d木が点の代わりに矩形または超矩形を格納する場合がある。2次元の矩形は4次元のオブジェクト (x, x, y, y) とみなすことができる。したがって、矩形範囲探索は、その矩形範囲に重なる全ての矩形を求める問題となる。木構造は通常、各葉ノードが矩形に対応するように構築される。直交範囲検索では、中央値との比較に反対側の座標値を用いる。例えば、現在のレベルの分割が x に沿って行われているなら、探索矩形の x の座標値を用いる。中央値が探索矩形の x より小さいなら、左側の分枝には探索矩形と重なるものがないと判断でき、刈り取ることができる。さもなくば、両方の分枝を走査する必要がある。これの1次元の特殊ケースを区間木と呼ぶ。

出典:wikipedia