2

我一直在尝试从头开始实现 KdTree。成功实现了 add-，find最近的邻居，find 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和没有意义。nullt.right with remove(t.right, ...)

这是正确的吗？当我们这样做的时候，这种方法还有什么问题吗？应该注意的是，与这些幻灯片中描述的方法相反，我将相等的节点放在左边，而不是右边。方法还有效吗？

4

1 回答 1

2

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

您需要替换节点，因为两个子节点都没有使用正确的拆分轴，因此如果子树更改级别，则子树无效。最小右值或最大左值仍会将点划分为同一轴，因此可用于替换。

于 2011-11-01T22:22:46.150 回答