gpt4 book ai didi

algorithm - KdTree 节点移除

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:53:18 25 4
gpt4 key购买 nike

我一直在尝试从头开始实现 KdTree。成功实现添加、查找最近邻居和在范围方法中查找节点后,我现在被困在删除节点上。

维基百科上描述的方法含糊不清,而且毫无用处。相反,我使用 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 替换为 remove(t.right, ...) 是没有意义的。

这是正确的吗?在我们讨论的过程中,这种方法还有什么问题吗?应该注意的是,与这些幻灯片中描述的方法相反,我将相等的节点放在左侧,而不是右侧。该方法是否仍然有效?

最佳答案

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

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

关于algorithm - KdTree 节点移除,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7970966/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com