3次元のkd木。根セル(白)をまず2つの部分セルに分割(赤)し、それぞれをさらに2つに分割(緑)している。最後に4つのセルそれぞれを2つに分割(青)している。それ以上の分割はされていないので、最終的にできた8つのセルを葉セルと呼ぶ。黄色の球は木の頂点を表している。 kd木(英: kd-tree, k-dimensional tree)は、k次元のユークリッド空間にある点を分類する空間分割データ構造である。kd木は、多次元探索鍵を使った探索(例えば、範囲探索や最近傍探索)などの用途に使われるデータ構造である。kd木はBSP木の特殊ケースである。 kd木は、座標軸の1つに垂直な平面だけを使って分割を行う。BSP木では分割平面の角度は任意である。さらに一般的には、kd木の根ノードから葉ノードまでの各ノードには1つの点が格納される[1]。この点もBSP木とは異なり、BSP木では葉ノードのみが点(ま
![kd木 - Wikipedia](https://cdn-ak-scissors.b.st-hatena.com/image/square/38a1ca02f2dab61f04ffca7dc0826ab66c8f342c/height=288;version=1;width=512/https%3A%2F%2Fupload.wikimedia.org%2Fwikipedia%2Fcommons%2Fb%2Fb6%2F3dtree.png)