k-d树的构建与搜索

1. k-d 树的构建

k-d 树（k-dimensional tree）是一种用来组织 k 维空间中点集的二叉搜索树。它的核心思想是轮流选择一个维度作为划分标准，将空间递归地一分为二。

• 划分原则: 在每个节点，我们选择一个维度，然后找出该维度上所有点的中位数作为划分值。
• 节点与子树: 所有在该维度上值小于或等于中位数的点，构成左子树；所有大于中位数的点，构成右子树。
• 轮流划分: 每下一层节点，划分维度会切换到下一个，例如：根节点用 x 轴，子节点用 y 轴，孙子节点再用 x 轴，以此类推。

2. k-d 树的最近邻搜索

搜索新点的最近邻是一个先定位后优化的过程。

A. 搜索路径：定位候选点

• 从根节点开始，根据新点在当前划分维度上的值，像在二叉搜索树中一样，递归地向下遍历。
• 这个过程直到到达一个叶子节点，这个叶子节点上的点就是第一个候选最近邻点。
• 计算新点与该候选点的距离，将此距离设为当前的最短距离 $D_{min}$。

B. 回溯与剪枝：优化搜索

• 从叶子节点开始，沿着搜索路径回溯。
• 在每个回溯的节点，我们都要判断是否存在比当前 $D_{min}$ 更短的距离。
• 剪枝判断: 检查新点到当前节点划分超平面的距离。
  • 如果新点到划分超平面的距离大于或等于 $D{min}$ ，说明另一个子树中不可能存在比 $D{min}$ 更近的点。此时，可以直接剪枝，跳过对那个子树的搜索。
  • 如果新点到划分超平面的距离小于 $D{min}$ ，说明另一个子树中可能存在更近的点，我们必须进入该子树继续搜索，并更新 $D{min}$ 。

通过不断地回溯和剪枝，我们最终能找到真正的最近邻点。