2

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

質問

  1. 最後から2番目の行の「i」はどういう意味ですか？（他の場所で参照されていないため、これは作成者による間違いかもしれませんか？）

  2. 「whichAxis」とは正確には何ですか？最も近くになりたい分割超平面の深さですか？

  3. 最小化する「minimum（）」とは何ですか？これは軸までの距離ですが、作者がポイントを最小化しているように見えますが、これは私には意味がありません。

4

2 に答える 2

4

（1）私はタイプミスだと思います。 私はそれの実装にそのようなものを持っていません、そしてそれはうまくいくようです（有名な最後の言葉..）。

（2）whichAxisは、最小値を検索している平面です。したがって、2次元データでは、xまたはyのいずれかになります。たとえば、ポイント（20,40）と（40,20）の場合、一方はxで最小になり、もう一方はyで最小になります。置換ノードの検索を開始するときは、検索する必要のある分割平面を知っておく必要があります。

（3）スライドの書き方が少し変です。適切な平面で最小値を見つけたいと考えています。多分これは少し明確になります（c＃）。私の実装は、東向きと北向きをxとyとして使用するデータセット用です。minAxisは、平面が2つしかないため、単なるブール値です。

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

...ここで、leftとrightは、現在のノードの左右の子ツリーから再帰的に検索される最小値です。より明確になれば、完全な関数を投稿できます:-)

于 2010-03-17T11:55:07.223 に答える
2

特定のkdツリー内のnodeAを削除する場合

（1）nodeAがリーフノードの場合は、nullにするだけです

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

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)

ノート：

nodeBがnodeA.rightの下にnodeAと等しい場合は、2を選択する必要があります

nodeBがnodeA.leftの下にnodeAと等しい場合は、1を選択する必要があります。

その後、nodeAをnodeBに置き換え、nodeBを削除します。

于 2013-05-22T04:23:33.307 に答える