KdTree节点去除

Question

我一直试图从头开始实现一个KdTree。成功地实现了add-，查找最近的邻居-并在range方法中找到节点，我现在被困在节点的删除上。

维基百科上描述的方法是模糊的和相当无用的。相反，我使用这些幻灯片作为起点。然而，对幻灯片13上的删除方法的描述让我感到困惑：

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

当您移除一个不是叶的节点时，必须从一个子树中用一个叶节点替换它。这意味着叶节点父节点需要获得一个空指针，而叶节点本身需要将其指针设置为被替换节点中的那些值。

您需要替换该节点，因为两个子节点都没有使用正确的拆分轴，因此如果子树更改了级别，那么子树就无效。一个最小的右值或最大的左值仍然会将点分割成一个相同的轴，因此会被用于替换。