KD-Tree找到最近的邻居时访问了哪些节点

Question

鉴于这些点（7,3），（10,5），（9,0），（5,8），（3,2），（8,1），我需要创建一个平衡的KD树，例如KD树的第一层沿x轴分割，当有两个中位数时，我们选择“较大”的一个作为子树的根。构建完之后，我需要列出尝试找到该点（2,4）的最近邻居时访问的节点。这是我使用上面给定的点构建的树：Here is the KD-Tree I've built

我对寻找最近的邻居非常困惑，而且我必须列出当树找到点（2,4）时访问的节点。到目前为止，我认为它访问（8,1）->（7,3）->（5,8）。但是之后呢？访问哪些节点？

Answer 1

您的k-d树是正确的。

最近邻居算法

k-d树最近邻居搜索通过在两个阶段之间交替来遍历树：

1. 下降阶段：

   • 注意输入点与树中当前节点之间的距离（实际距离，而不是轴上的距离。

   • 在x轴和y轴之间交替，将输入点的轴坐标与树中当前节点的轴坐标进行比较，以确定要下降到的子树。

   • 重复上载阶段，直到到达树的底部，然后进入上载阶段。

2. 备份阶段：

   • 上一层。如果你不能上去，那就完成了。

   • 如果您已经在当前节点的两个子树上执行了Go-down阶段，请重复Go-back-up。

   • 如果您到目前为止找到的最佳邻居的实际距离比输入节点和树中当前节点之间的轴距离更近，请重复执行上移。

   • 否则，请在与您所在的树相对的子树上进入下移阶段。

您的示例

这里是您的k-d树的草图，以使其更加清晰：

在示例树和输入节点（2,4）上应用这些步骤：

• 从根节点（8,1）的下降阶段开始。（8,1）与输入节点（2,4）之间的距离为6.708，因此（8,1）是我们当前已知的最近邻居。当前轴是x，因此我们将8和2进行比较，看到我们必须转到左侧的子树。
• 当前节点是（7,3）。 （7,3）与输入节点（2,4）之间的距离为5.099，这比以前的最著名距离要好，因此（7,3）成为我们新的最近邻居。当前轴是y，因此我们将3和4进行比较，然后看到必须转到右侧的子树。
• 当前节点是（5,8）。 （5,8）与输入节点（2,4）之间的距离为5.000，小于先前的最著名距离，因此（5,8）成为我们的新近邻居。当前轴是x，但是我们不能再向下移动，因此我们进入Go-back-up阶段。
• 我们回到（7,3）。当前轴为y。 （7,3）与输入节点（2,4）之间的y距离是| 3-4 |。 = 1，小于5，即到当前已知的最近邻居的距离。因此，我们必须在另一个子树上进入Go-back-down阶段。您可以在图中看到它：输入点（S）与（5,8）之间的距离大于（S）与经过（7,3）的分隔线之间的距离。这意味着分隔线的另一侧可能有一个更近的邻居。
• 当前节点是（3,2）。 （3,2）与输入节点（2,4）之间的距离为2.236，比以前已知的最佳距离好，因此（3,2）成为我们当前已知的最近邻居。当前轴是x，但是我们不能再走了，所以我们进入Go-back-up阶段。
• 我们回到（7,3）。当前轴为y。我们访问了该节点的两个子树，因此我们重复执行Go-back-up阶段。
• 我们回到（8,1）。当前轴是x。 （8,1）与输入节点（2,4）之间的x距离是| 8-2 |。 = 6，它大于到当前已知的最近邻居的距离，因此我们重复Go-back-up阶段。您可以在图片中再次看到它：输入点（S）与当前最近的邻居（3,2）之间的距离小于（S）与经过（8,1）的分隔线之间的距离。这意味着分隔线的另一侧不能有更近的邻居。
• 我们不能再进一步了，所以我们完成了。

我们访问的节点在：（8,1），（7,3），（5,8），（7,3），（3,2），（7,3），（8,1）。我们发现的最近邻居是（3,2），距离为2.236。