刪除KdTree節點

Question

我一直在嘗試從頭開始實施KdTree。在成功實現add-，找到最近的鄰居並在範圍方法中找到節點之後，我現在堅持刪除節點。

維基百科上描述的方法含糊不清，而且毫無用處。相反，我使用these slides作爲起點。然而，在幻燈片13 remove方法的說明混淆了我：

KDNode remove (KDNode t , Point p , int cd) { 
if (t == null) return null; 
else if (p.cd < t.data) t.left = remove (t.left , p , cd +1); 
else if (p.cd > t.data) t.right = remove (t.right , p , cd +1); 
else { 
    if (t.right == null && t.left == null) return null ; 
    if (t.right != null) 
    t.data = findmin(t.right , cd , cd +1); 
    else { 
    t.data = findmin (t.left , cd , cd +1); 
    t.left = null; 
} 

t.right = remove (t.right , t . data , cd +1); 
return t ; 
}} 

兩個替代t.left與null和t.right with remove(t.right, ...)是沒有意義的。

這是正確的，雖然我們在這個方法有什麼問題嗎？應該指出的是，與這些幻燈片中描述的方法相反，我將相同的節點放在左側，而不是右側。該方法仍然有效嗎？

Answer 1

當您刪除不是葉的節點時，您必須用替換它與來自其中一個子樹的葉節點。這意味着葉節點父節點需要獲得NULL指針，葉節點本身需要將其指針設置爲被替換節點中的值。

您需要替換節點，因爲子節點都沒有使用正確的拆分軸，所以如果子樹更改級別，則子樹無效。最小右值或最大左值仍然將這些點劃分爲同一個軸，因此可用於替換。