K-d树（K-dimensional Tree）

K-d树是一种用于组织k维空间中点数据的数据结构，它是一种特殊的二叉搜索树，主要用于多维数据的快速范围查询和最近邻搜索。

1. 基本概念
想象一下，你有一个包含许多地址的数据库，每个地址都有经度和纬度（两个维度）。如果你想快速找出某个位置附近1公里内的所有地址，或者找出离某个点最近的一个地址，K-d树就能高效地完成这类任务。它的核心思想是递归地将k维空间进行划分，每个划分节点都代表一个超平面，该超平面垂直于某个坐标轴。

2. K-d树的构建过程
构建K-d树的过程就是递归地将点集划分为两个子空间的过程。

• 步骤1：选择划分维度
  在树的每一层，我们都需要选择一个维度（或坐标轴）来进行划分。最常用的策略是循环选择。例如，在根节点（第0层），我们选择第1个维度（x轴）进行划分；在下一层（第1层），选择第2个维度（y轴）；再下一层（第2层），如果存在第三个维度就选z轴，否则循环回第1个维度（x轴），以此类推。另一种策略是选择方差最大的维度进行划分，这样可能产生更平衡的树，但计算成本更高。

• 步骤2：确定划分点
  选定了划分维度后，我们需要在当前点集中找到一个“中点”作为划分点。这个点将把当前空间一分为二。理想的做法是选择当前点集在划分维度上的中位数作为划分点。这样能保证构建出的树是平衡的，左子树和右子树包含的点数大致相等。

• 步骤3：递归构建
  确定了划分点和划分维度后，划分点就成为当前树的根节点。然后，我们将剩余的点分为两组：

  • 在划分维度上，值小于划分点的点，归入左子树。
  • 在划分维度上，值大于等于划分点的点，归入右子树。
    对左子点集和右子点集递归地重复步骤1和步骤2，直到点集为空。

让我们通过一个二维例子来具体说明：
假设我们有二维空间中的点集：[(7,2), (5,4), (9,6), (4,7), (8,1), (2,3)]。

1. 根节点（第0层，划分维度：x轴）：

   • 对x坐标排序：2, 4, 5, 7, 8, 9。中位数是(7,2)或(5,4)？实际上，我们取中位数点。这里点集是偶数个，可以选择第3个（从1开始计数）或第4个点。我们选择(7,2)作为根节点（x=7）。
   • 划分：x < 7的点 [(5,4), (4,7), (2,3)] 进入左子树；x >= 7的点 [(9,6), (8,1)] 进入右子树。

2. 根节点的左子树（第1层，划分维度：y轴）：

   • 点集为 [(5,4), (4,7), (2,3)]。对y坐标排序：3, 4, 7。中位数点是(5,4)（y=4）。
   • 划分：y < 4的点 [(2,3)] 成为左子节点；y >= 4的点 [(4,7)] 成为右子节点。

3. 根节点的右子树（第1层，划分维度：y轴）：

   • 点集为 [(9,6), (8,1)]。对y坐标排序：1, 6。中位数点可以选择(8,1)或(9,6)。我们选择(9,6)（y=6）。
   • 划分：y < 6的点 [(8,1)] 成为左子节点；右子树为空。

最终构建的K-d树结构如下图所示（想象一棵二叉树）：

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

3. K-d树的搜索：最近邻搜索
这是K-d树最经典的应用。目标是找到树中距离目标点最近的点。

• 步骤1：下行查找近似最近点
  从根节点开始，像在二叉搜索树中一样，根据当前层的划分维度，与节点比较，递归地向下搜索，直到叶子节点。这个路径上的叶子节点就是目标点的“近似最近邻”。

• 步骤2：回溯与剪枝
  这是算法的关键。得到近似最近邻后，需要回溯到父节点，检查是否存在更近的点。

  1. 计算当前得到的最短距离。
  2. 回溯到父节点，检查父节点的另一侧子树（与搜索路径相反的一侧）中是否可能存在更近的点。
  3. 如何判断？以目标点为圆心，以当前最短距离为半径画一个“超球体”。如果这个球体与父节点所在的划分超平面相交，就意味着另一侧子树中可能存在更近的点，需要进入另一侧子树进行搜索。如果不相交，则另一侧子树不可能有更近的点，可以剪枝，跳过整个子树的搜索。

• 步骤3：更新最近点
  如果进入另一侧子树搜索，找到了更近的点，就更新当前最近点和最短距离。然后继续回溯，直到回溯到根节点。

举例：在上面建的树中，查找点(8,3)的最近邻。

1. 下行搜索：比较(8,3)和根(7,2)（x轴维度：8>7）-> 右子树。比较(8,3)和(9,6)（y轴维度：3<6）-> 左子树，到达(8,1)。近似最近邻是(8,1)，距离为2。
2. 回溯到(9,6)：计算(8,3)到(9,6)的距离（约3.6）>2，不更新。检查另一侧（右）子树：为空。
3. 回溯到根(7,2)：计算(8,3)到(7,2)的距离（约1.41）<2，更新最近邻为(7,2)，最短距离为~1.41。
4. 关键剪枝：检查根节点的另一侧（左）子树。目标点(8,3)到划分超平面（x=7）的距离是1。而当前最短距离是1.41。因为1 < 1.41，意味着以(8,3)为圆心、1.41为半径的圆与x=7这条直线相交。因此，左子树中可能存在更近的点，不能剪枝，必须搜索左子树。
5. 搜索左子树：从(5,4)开始，比较(8,3)和(5,4)（y轴维度：3<4）-> 左子树，到达(2,3)。计算距离(8,3)到(2,3)为6，大于1.41，不更新。回溯到(5,4)，计算到(5,4)的距离（约3.16）>1.41，不更新。检查另一侧（右）子树(4,7)，距离更远。最终确定最近邻是(7,2)。

4. 复杂度与优缺点

• 构建复杂度：如果每次都能找到中位数，构建平衡K-d树的时间复杂度是O(n log n)。空间复杂度是O(n)。
• 查询复杂度：对于最近邻搜索，在低维空间中，平均情况下的时间复杂度是O(log n)，最坏情况（如数据分布极不均匀）是O(n)。
• 优点：对于低维数据的最近邻和范围搜索非常高效。
• 缺点：当数据维度很高时（例如超过10维），所谓的“维度灾难”会出现，搜索效率会退化成接近线性扫描O(n)，因为超球体几乎总会与划分超平面相交，导致剪枝策略失效。