Kd木
n個の点から静的なkd木を構築する場合、中央値を求めるアルゴリズムで変わる。 単純にO(n log n) のソートを使って中央値を各レベルについて計算するとすると、全体として O(n log n) の時間がかかる。 より高速な線形中央値探索アルゴリズム(例えば Cormen et al)を使う場合、計算量は O(n log n) になる。
平衡kd木への新たな点の挿入には、O(log n) の時間がかかる。
平衡kd木からの点の削除には、O(log n) の時間がかかる。
平衡kd木である軸に平行な範囲にある点を求める場合、 O(n +k) の時間がかかる。ここで、k は報告される点の個数、d は kd木の次元である。
kd木から1つの点を削除する場合、不変量が維持されるようにしなければならない。最も簡単な方法は、削除したい点に対応するノードから下の全ノードについて、対応する全ての点についてkd木を再構築することである。ノードの軸およびピボット値を保持する必要がある。