5

这是我对它的理解： 1. 向下递归，根据 ELEMENT 是否存在于左子树或右子树中取左子树或右子树。2. 将 CURRENT_BEST 设置为您到达的第一个叶节点。3. 当你递归备份时，检查 ELEMENT 是否离分裂超平面比离 CURRENT_BEST 更近。如果是这样，请将 CURRENT_BEST 设置为当前节点。

这是我从Wikipedia和我的班级得到的部分，也是我不明白的部分： 4.检查3.中挑出的分裂点的另一个子树中的任何节点是否比分裂点更接近ELEMENT .

我不明白为什么我们需要做 4.，因为可能位于分裂节点的一个子树中的任何点都必须比另一个子树中的任何点更靠近分裂节点。

显然，我对算法的理解存在缺陷，因此将不胜感激。

4

3 回答 3

9

第 4 步是第 3 步中的“其他”，如果平面比该点更近，您会做什么。仅仅因为您找到的点与您正在寻找邻居的点在同一个矩形中并不意味着它是最近的。

想象一下下面的场景：你的 kD-Tree 中有两个点，A 和 B。A 在它的矩形的中间，而 B 刚好在边缘的上方，在 A 旁边的分区区域中。如果你现在搜索对于点 C 的最近邻居，它紧邻 B 但恰好是边缘的另一侧并且在 A 的分区区域中，由于初始深度优先搜索选择任何内容，您选择的第一个点将是 A将与您的搜索点位于同一分区中。但是，B 实际上更接近，所以即使您选择了 A，您也需要检查 B 是否更接近，否则您的 kD-Tree 实际上不会给您正确的结果。

将其可视化的一个好方法是将其绘制出来：

A-------------C--|--B

A 是我们在 DFS 中找到的第一个点，C 是我们想要最近邻的点，B 是实际最近邻，| 是我们的分裂平面。

另一种思考方式是在点 C 周围画一个半径为 dist(A,C) 的圆。如果任何其他矩形的任何部分都落在这个圆内，那么它们就有可能持有一个点，该点可能是比 A 更接近 C，因此必须检查它们。如果你现在找到 B，你可以减少你的圆的半径（因为 B 更接近），这样更少的矩形有相交的机会，并且一旦你检查了所有与你的圆相交的矩形（减少你的圆半径作为你的找到更近的邻居）你可以明确地说没有更近的点。

于 2012-12-14T14:43:14.353 回答
2

我在 github 上写了一个基本的C++ 实现。它具有迭代和递归版本。

于 2012-12-05T07:59:08.180 回答
-4 
function kdtree (list of points pointList, int depth)
{
    // Select axis based on depth so that axis cycles through all valid values
    var int axis := depth mod k;

    // Sort point list and choose median as pivot element
    select median by axis from pointList;

    // Create node and construct subtrees
    var tree_node node;
    node.location := median;
    node.leftChild := kdtree(points in pointList before median, depth+1);
    node.rightChild := kdtree(points in pointList after median, depth+1);
    return node;
}
于 2012-11-22T07:15:52.877 回答