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

Question

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

但是，有人说我从计算几何算法和应用程序(De Berg、Cheong、Van Kreveld 和 Overmars)研究 Kd 树，第 5.2 节，第 99 页。我能看到的主要区别是 Overmars 放置了拆分数据在内部节点和叶子中数据集的实际点。例如，在 2D 中，内部节点将保持分割线。

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

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

Answer 1

默认的 k-d-trees 应该在一个点上分割数据集。然后将这个点存储在内部节点上，并在搜索时沿着这棵树向下走时检查是否为邻居。

当然你可以有 k-d-trees 的各种变体，其中 split 可能在不同的地方，当 split 位置没有元素时，你不能再在内部节点中有一个。

另外，由于 k-d-trees 不是动态的，当通过墓碑模拟删除时，内部节点可能只包含墓碑(代表已删除的对象)。