Kd木
kd木の平衡化は注意を要する。kd木は多次元に渡ってソートされているため、一般的な木の回転 (tree rotation) を行って平衡化すると、不変量が保持されなくなる。
kd木に含まれない点が与えられ、その点に最も近いkd木上の点を探す問題を考える(最近傍探索)。この場合、単純なテストで木の大部分を捨てられることを利用する。この場合、木構造を深さ優先探索で走査し、各段階で最短距離の近似計算を行う。アルゴリズム上より近傍の点がないと判断されたとき、最近傍が決定され、終了する。
まず、最短距離を無限としておいて、根ノードを調べる。次に、与えられた点を含む右または左の部分領域(それぞれ超矩形になっている。3次元の場合は直方体)を探す。これを繰り返していって、与えられた点を含む最小の領域(葉ノード)を求める。次に上方向に再帰的に、親ノードのもう一方の領域がより近い点を持っていないかを調べていく。これは、与えられた点を中心として半径が現在の最近傍の点までの距離となる超球(3次元なら単なる球)と各領域の超矩形とが重なるかどうかを調べることでなされる。