K-维树（K-d Tree）的构建与查询

K-d树是一种用于组织k维空间中点的数据结构，广泛应用于范围搜索、最近邻搜索等场景。今天我们将深入探讨K-d树的构建过程和核心查询操作。

1. 基本概念
K-d树是二叉搜索树在多维空间的扩展，每个节点代表一个k维点。树中每一层都按某个特定维度进行划分（通常循环使用各维度），从而将空间递归分割成超矩形区域。

2. 构建过程
假设我们要为点集[(2,3), (5,4), (9,6), (4,7), (8,1), (7,2)]构建2-d树：

步骤1：选择根节点

• 第一层按x维度划分（深度0对应维度0）
• 对x坐标排序：2,4,5,7,8,9 → 中位数是7（对应点(7,2)）
• 根节点为(7,2)，划分平面x=7将空间分为左右两部分

步骤2：递归构建左子树

• 左子节点集：[(2,3), (5,4), (4,7)]（x≤7）
• 第二层按y维度划分（深度1对应维度1）
• 对y坐标排序：3,4,7 → 中位数4（对应点(5,4)）
• 左子树根节点为(5,4)，划分平面y=4

步骤3：递归构建右子树

• 右子节点集：[(9,6), (8,1)]（x>7）
• 按y维度排序：1,6 → 中位数6（对应点(9,6)）
• 右子树根节点为(9,6)，划分平面y=6

步骤4：继续细分

• (5,4)的左子节点：y≤4的点[(2,3)]，按x维度划分
• (5,4)的右子节点：y>4的点[(4,7)]，按x维度划分
  最终构建的树结构：

        (7,2)
       /     \
   (5,4)     (9,6)
   /   \       /
(2,3) (4,7) (8,1)

3. 最近邻查询
以查询点(8,3)的最近邻为例：

步骤1：初始化

• 当前最近点：根节点(7,2)，距离√((8-7)²+(3-2)²)=√2
• 搜索路径：根节点→右子树（因为8>7）

步骤2：深度优先搜索

• 访问(9,6)：距离√5 > √2，不更新
• 回溯检查：查询点与分割平面y=6的距离|3-6|=3 > 当前最小距离√2，无需搜索左子树

步骤3：回溯到根节点

• 检查左子树：查询点与分割平面x=7的距离|8-7|=1 < 当前最小距离√2，需要搜索
• 访问(5,4)：距离√10 > √2，不更新
• 检查子树：查询点与y=4的距离|3-4|=1 < √2，需要搜索两个子树
• 访问(2,3)：距离√37 > √2
• 访问(4,7)：距离√26 > √2

步骤4：最终结果
最近邻点是(7,2)，距离√2

4. 算法要点

• 构建复杂度：O(n log n)（若使用线性时间中值选择可优化至O(n)）
• 查询复杂度：平均O(log n)，最坏O(n)
• 优化策略：维护优先队列存储候选点，及时剪枝

5. 应用场景

• 地理信息系统中的邻近搜索
• 计算机视觉的特征匹配
• 机器学习中的KNN算法加速

通过这种空间划分方式，K-d树能有效处理多维数据的邻近查询，其核心思想是通过轴对齐的划分将搜索空间快速缩小。