2 次元の kd ツリーから要素を削除する

Question

kd-tree (2D) クラスを拡張して、ノード (ポイント) を削除できるようにしたいと考えています。この削除は、ツリーの大部分を再構築することなく実行する必要があります。これらで説明されているアルゴリズムは、 スライド, スライド 13 が私が求めているもののようです。ただし、スライド 7 にあるノード削除アルゴリズムで使用される「findmin()」の説明を理解するのが困難です。

質問

1. 最後から 2 行目の「i」は何を意味しますか?(他では参照されていないので、おそらくこれは著者の間違いでしょうか?)

2. 「どの軸」とは正確には何ですか?それは、最も近づきたい分割超平面の深さでしょうか?

3. 最小化する「minimum()」とは何ですか?これは軸までの距離だろうと思ったのですが、著者がポイントを最小限に抑えているように見えて、意味がわかりません。

Answer 1

（1）私は<全角> のだと思うの私はのタイプミスです。私はそれの私の実装ではそのようなものを持っていない、正常に動作するように見える（有名な最後の言葉を...）。

（2）のwhichAxis のあなたが最小を探している平面である。2次元データで、それはxまたはyのいずれかになりますので。例えば。点（20,40）及び（40,20）のために、一方はxの最小値及びyの他方です。あなたは、交換ノードの検索を開始するとき、あなたはあなたが検索する必要がどの分割面を知っている必要があります。

（3）スライドを少し妙書き込まれます。あなたは適切な平面内の最小値を見つけたいです。多分これは少し（C＃）を明確にします。私の実装では、 eastingsとnorthingsは、xとyとを使用してデータセットのためのものです。私は今までに二つの面を持っているようminAxisは、単にブール値です。

bool winner = minAxis ? (left.Easting < right.Easting) : (left.Northing < right.Northing);
return winner ? left : right;

...ここで、の左と右の最小値は、再帰的に私たちがしているノードの左と右の子木から検索されている。私が投稿することができますフル機能、それが明確に行う場合： - ）

Answer 2

あなたが与えられたKDツリーでノードAを削除したい場合は、

（1）ノードAがリーフノードである場合、それがnullにする

（2）ノードAがリーフノードでない場合

Assume nodeA split by x , you have two choice

1. find the largest nodeB (whose X is the largest) in left   
2. find the minimum nodeB (whoes X is the minimum) in right  (This pdf prefer it)

注：

を使用すると、ノードBはnodeA.rightの下にノードAに等しい置けば、あなたが選ぶべき2 の

を使用すると、ノードBはnodeA.leftの下にノードAに等しい置けば、あなたが選択する必要があり、1 の

その後、ノードBとノードAを交換し、ノードBを削除します。