從兩維kd-tree中刪除一個元素

我想擴展kd-tree（2D）類以便能夠刪除節點（點）。應該在不需要重建樹的大部分的情況下進行該移除。在幻燈片13上的這些slides中描述的算法似乎是我所追求的。然而，我很難按照幻燈片7上找到的「findmin（）」的描述來使用節點移除算法。從兩維kd-tree中刪除一個元素

問題

什麼是「我」的意思是在倒數第二行？（也許這是作者的錯誤，因爲它在別處沒有引用？）
「whichAxis」到底是什麼？它是我們想要最接近的分裂超平面的深度嗎？
什麼是「最小（）」，最小化？我雖然這將是與軸的距離，但它看起來像作者正在最小化點，這對我來說沒有意義。

來源

2010-03-09 Nixuz

（1）I 認爲我是一個錯字;在我的實現中，我沒有這樣的東西，它看起來很好（最後一句話很有名）。

（2）whichAxis是您正在尋找最小值的平面。因此，在二維數據中，它將是x或y。例如。對於點（20,40）和（40,20），一個是x的最小值，另一個是y。當您開始搜索替換節點時，您應該知道要搜索哪個分割平面。

（3）幻燈片寫得有點奇怪。你想在適當的平面上找到最小值。也許這會澄清一點（C＃）。我的實現是使用eastings and northings作爲x和y的數據集。 minAxis只是一個布爾，因爲我只有兩架飛機。

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

...其中離開和右是最低值遞歸搜索，從我們在節點的左邊和右邊子樹。我可以張貼的全部功能，如果它使更清晰的:-)

來源

2010-03-17 11:55:07 Smigs

如果你想在一個給定的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)

注：

如果你把節點B nodeA.right下等於nodeA上，你應該選擇2

如果你把節點B nodeA上等於下了nodeA .left，您應該選擇1

然後，將nodeA替換爲nodeB並刪除nodeB。

來源

2013-05-22 04:23:33

從兩維kd-tree中刪除一個元素

回答

相關問題