kd木(英: kd-tree, k-dimensional tree)は、k次元のユークリッド空間にある点を分類する空間分割データ構造である。kd木は、多次元探索鍵を使った探索(例えば、範囲探索や最近傍探索)などの用途に使われるデータ構造である。kd木はBSP木の特殊ケースである。
kd木は、座標軸の1つに垂直な平面だけを使って分割を行う。BSP木では分割平面の角度は任意である。さらに一般的には、kd木の根ノードから葉ノードまでの各ノードには1つの点が格納される[1]。この点もBSP木とは異なり、BSP木では葉ノードのみが点(または他の幾何学的プリミティブ)を含む。つまり、kd木の各分割平面は必ず1つの点を通る。葉ノードのみがデータを格納する派生データ構造をkdトライと呼ぶ。また、特記すべきkd木の別の定義として、各分割平面が1つの点を通るよう決定されるものの、点を葉ノードでのみ記憶するという定義もある[2]。
[編集] kd木上の操作
[編集] kd木の構築
軸に対応した分割平面の選択方法は様々なものがあり、kd木の構築方法も様々である。典型的なkd木の構築方法は以下のようになる。
- 木構造を下降すると共に、分割平面を選択する軸を巡回するようにする。例えば、根においてx軸に垂直な平面とし、根の子ではy軸に垂直な平面とし、根の孫ではz軸に垂直な平面とする、というように軸を巡回するように選択していく。
- 各ステップで、分割平面生成で選択される点は、kd木に入れる全ての点の対応する軸の座標値の中央値となる点とする。なお、前提として全ての点の集合がアルゴリズムの先頭で得られるものとする。
この方法では平衡kd木が得られ、各葉ノードと根との距離は等しくなる。しかし平衡木があらゆる応用において最適とは限らない。
また、常に中央値となる点を選択することが求められているわけではない。中央値を気にしない場合、単に平衡木となることが保証されないだけである。中央値を選択するアルゴリズムやソートをしない場合のヒューリスティックとしては、固定個の点を無作為に選択し、それらの中の中央値を選んで分割するという方式がある。実用上はこの技法で十分平衡的な木が得られる。
n個の点のリストを与えられたとき、以下のアルゴリズムで平衡kd木を構築できる。
!doctype>