2D KD树和最近邻搜索
我正在按照此处描述的算法实现KD树和最近邻搜索： http ： //ldots.org/kdtree/
我遇到了几种不同的方法来实现KD树，其中一个点存储在内部节点中，另一个只存储在叶节点中。 因为我有一个非常简单的用例（我需要做的只是构造一次树，它不需要修改），我采用了仅叶子的方法，它实现起来似乎更简单。 我已成功实现了所有内容，树总是成功构建，并且在大多数情况下，最近邻搜索返回正确的值。 但是，我有一些问题，对于某些数据集和搜索点，算法返回不正确的值。 考虑一下要点：
[[6, 1], [5, 5], [9, 6], [3, 81], [4, 9], [4, 0], [7, 9], [2, 9], [6, 74]] 构建一个看起来像这样的树（借口我糟糕的图表）： 
方形叶节点是包含点的节点，并且圆形节点包含用于在该深度处分割列表的中值。 当在这个数据集上调用我的最近邻居搜索，并寻找[6, 74]的最近邻居时，算法返回[7, 9] 。 虽然这正确地遵循算法，但它实际上并不是[6, 74]的最接近点。 最近的点实际上是[3, 81] ，其距离为7.6， [7, 9]距离为65。
以下是绘制的点，对于可视化，红点是我试图找到最近邻居的点：
如果有帮助，我的搜索方法如下：
private LeafNode search(int depth, Point point, KDNode node) { if(node instanceof LeafNode) return (LeafNode)node; else { MedianNode medianNode = (MedianNode) node; double meanValue = medianNode.getValue(); double comparisonValue = 0; if(valueEven(depth)) { comparisonValue = point.getX(); } else { comparisonValue = point.getY(); } KDNode nextNode; if(comparisonValue < meanValue) { if (node.getLeft() != null) nextNode = node.getLeft(); else nextNode = node.getRight(); } else { if (node.getRight() != null) nextNode = node.getRight(); else nextNode = node.getLeft(); } return search(depth + 1, point, nextNode); } }
所以我的问题是：
-
这是对KD树中最近邻搜索的期望，还是我应该得到最接近我要搜索的点的点（因为这是我使用树的唯一原因）？
-
这只是这种forms的KD树的问题，我应该将其更改为存储内部节点中的点来解决这个问题吗？
KD树的正确实现总是找到最近的点（如果点仅存储在叶子中，则无关紧要）。 但是，您的搜索方法不正确。 它应该是这样的：
bestDistance = INF def getClosest(node, point) if node is null return // I will assume that this node splits points // by their x coordinate for the sake of brevity. if node is a leaf // updateAnswer updates bestDistance value // and keeps track of the closest point to the given one. updateAnswer(node.point, point) else middleX = node.median if point.x < middleX getClosest(node.left, point) if node.right.minX - point.x < bestDistance getClosest(node.right, point) else getClosest(node.right, point) if point.x - node.left.maxX < bestDistance getClosest(node.left, point)
在ldots.org上给出的解释是完全错误的（以及搜索KD树的许多其他Google搜索结果）。
有关正确的实施，请参阅https://stackoverflow.com/a/37107030/591720 。