Kd木
中央値を選択するアルゴリズムやソートをしない場合のヒューリスティックとしては、固定個の点を無作為に選択し、それらの中の中央値を選んで分割するという方式がある。実用上はこの技法で十分平衡的な木が得られる。
n個の点のリストを与えられたとき、以下のアルゴリズムで平衡kd木を構築できる。
中央値より後ろ(after)の点には、中央値以上の座標値の点を含ませるのが一般的である。別の手法として、他の次元で点を比較する「スーパーキー(superkey)」関数を定義する方法もある。他にも、中央値に等しい点を両側に属させることもありうる。
このアルゴリズムをPythonで実装すると次のようになる。
このアルゴリズムは任意のノードについて不変条件を生成し、左の部分木にある全ノードは分割平面の一方の側にあり、右の部分木にある全ノードは同じ分割平面のもう一方の側にある。分割平面上にある点はどちらの側にも出現する可能性がある。あるノードの分割平面はそのノードに対応した点を通る(上記コードでは node.location で表されている)。