K-维树（K-d Tree）的最近邻搜索算法

1. 问题描述
最近邻搜索是K-d树的核心应用之一，目标是在k维空间中找到距离给定查询点最近的数据点。例如，在二维空间中，给定一组点集和查询点Q，快速找到点集中与Q欧氏距离最近的点。K-d树通过空间划分将搜索复杂度从O(n)优化至平均O(log n)。

2. K-d树结构回顾

• K-d树是二叉搜索树的多维扩展，每个节点代表一个k维点。
• 树的每一层按不同维度划分空间：根节点按第1维划分，下一层按第2维，依此循环。
• 每个节点包含：划分维度（axis）、划分值（split value）、左子树（包含划分维度值小于split的点）、右子树（包含大于等于split的点）。

3. 最近邻搜索步骤
步骤1：初始化

• 从根节点开始，设置当前最近点（current best）为null，最小距离（min_dist）为无穷大。

步骤2：递归向下搜索（类似二叉搜索）

• 从根节点出发，根据查询点Q在当前划分维度的值，选择左或右子树递归搜索（例如，若Q的当前维值小于节点值，进入左子树）。
• 递归过程中，每访问一个节点，计算Q与该节点的距离。若小于min_dist，更新current best和min_dist。

步骤3：回溯检查另一子树（关键优化）

• 完成当前分支的搜索后，需判断另一子树是否可能存在更近的点：
  • 计算Q到当前节点划分超平面的距离（即Q在当前划分维度与节点值的差值绝对值）。
  • 若该距离小于当前min_dist，说明另一子树可能包含更近点，需进入另一子树递归搜索。
  • 原理：以二维为例，若按x轴划分，当前min_dist为d，但Q到划分线的垂直距离小于d，则另一侧仍可能存在点与Q的距离小于d（如图形中圆形搜索区域与划分线相交）。

步骤4：终止条件

• 当节点为叶子节点，且所有必要分支搜索完成时结束。

4. 举例说明（二维空间）
点集：[(2,3), (5,4), (9,6), (4,7), (8,1), (7,2)]，构建的K-d树如下（按x/y轴交替划分）：

        (7,2)  [根节点，按x轴划分]
       /     \
   (5,4)     (9,6)  [第二层按y轴划分]
   /   \        \
(2,3) (4,7)   (8,1)

查询点Q = (6,3)：

1. 从根(7,2)开始：Q.x=6<7，进入左子树(5,4)。
2. 在(5,4)：Q.y=3<4，进入左子树(2,3)。
3. 到达(2,3)，距离Q≈4.12，更新min_dist。回溯到(5,4)。
4. 检查右子树(4,7)：Q到(5,4)划分线（y=4）的垂直距离|3-4|=1<min_dist，需搜索右子树。在(4,7)距离Q≈4.12，未更新。
5. 回溯到根(7,2)，计算Q到划分线（x=7）的距离|6-7|=1<min_dist，需搜索右子树(9,6)。
6. 在(9,6)距离Q≈4.24，不更新。其左子树空，回溯结束。
   最终最近点为(2,3)或(4,7)。

5. 复杂度分析

• 平均情况：O(log n)，最坏情况（如点集分布极不均衡）退化为O(n)。
• 优化技巧：
  • 优先搜索更近的分支。
  • 使用平方距离避免开方计算。

6. 应用场景

• 机器学习中的KNN算法加速、空间数据库、计算机图形学中的碰撞检测等。