algorithm - kd-tree 在内部节点中存储点？如果是，如何搜索NN？

Question

维基百科中关于 kd-trees 在内部节点中存储点的链接。我必须执行 NN 查询，我认为（这里是新手），我理解这个概念。

但是，据说我从 Computational Geometry Algorithms and Applications（De Berg、Cheong、Van Kreveld 和 Overmars），第 5.2 节，第 99 页研究 Kd 树。我可以看到的主要区别是 Overmars 将拆分数据放在内部节点和叶子中数据集的实际点。例如，在 2D 中，内部节点将保存分割线。

另一方面，维基百科似乎将点存储在内部节点和叶子中（而 Overmars 仅在叶子上）。

在这种情况下，我们如何执行最近邻搜索？此外，为什么会有这种差异？

Answer 1

默认的 kd-trees 应该在一个点分割数据集。然后这个点被存储在内部节点上，当你在搜索时沿着这棵树走时，它会被检查为邻居。

当然，您可以拥有各种 kd-trees 变体，其中拆分可能位于不同的位置，并且当没有元素恰好位于拆分位置时，您不能再在内部节点中拥有一个。

此外，由于 kd-trees 不是动态的，当通过 tombstone 模拟删除时，内部节点可能只包含一个 tombstone（表示已删除的对象）。