About: Kd木

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