Kd木
kd木(英: kd-tree, k-dimensional tree)は、k次元のユークリッド空間にある点を分類する空間分割データ構造である。kd木は、多次元探索鍵を使った探索(例えば、範囲探索や最近傍探索)などの用途に使われるデータ構造である。kd木はBSP木の特殊ケースである。
kd木は、座標軸の1つに垂直な平面だけを使って分割を行う。BSP木では分割平面の角度は任意である。さらに一般的には、kd木の根ノードから葉ノードまでの各ノードには1つの点が格納される。この点もBSP木とは異なり、BSP木では葉ノードのみが点(または他の幾何学的プリミティブ)を含む。つまり、kd木の各分割平面は必ず1つの点を通る。葉ノードのみがデータを格納する派生データ構造をkdトライと呼ぶ。また、特記すべきkd木の別の定義として、各分割平面が1つの点を通るよう決定されるものの、点を葉ノードでのみ記憶するという定義もある。