KD-Tree 算法原理与最近邻搜索实践
1. 概述
KD-Tree（K-Dimensional Tree），全称 K 维空间树，是一种用于组织 K 维空间中点数据的数据结构。它是二叉搜索树（BST）在多维空间上的扩展，也被称为'二叉'空间分割树。无论维度 K 是多少，KD-Tree 的每个节点都只有左和右两个子树。
核心思想：通过交替使用不同的维度作为分割轴，递归地将 K 维空间划分为若干个更小的区域，从而高效地进行范围搜索和最近邻搜索。该算法在任意维度 K 的最近邻搜索和范围搜索中表现优异，尤其在中低维（K<20）场景下效果显著。
类比：可以将其想象成一个在多维空间下不断'切蛋糕'的过程。例如在 2D 空间下，首先垂直切一刀，然后水平切一刀，再垂直切……如此反复，将空间划分为许多矩形区域。
2. 原理与构建
2.1 数据结构
树中的每个节点代表一个 K 维点，并包含以下信息：
- 数据点：该节点所代表的 K 维坐标。
- 分割维度：当前节点是根据哪个维度进行分割的（例如，0 代表 x 轴，1 代表 y 轴）。
- 左子树：包含所有在当前分割维度上值小于该节点值的点。
- 右子树：包含所有在当前分割维度上值大于或等于该节点值的点。
2.2 算法原理
- 分割方式：在构建树的每一层，KD-Tree 只选用一个特定的维度（比如第 i 维）来进行分割，它用一个垂直于该维度坐标轴的超平面将整个空间一分为二。
- 判断规则：对于空间中的任何一个点，判断它属于左子树还是右子树的规则非常简单：
- 左子树：该点在第 i 维上的坐标值 小于 当前节点的第 i 维坐标值。
- 右子树：该点在第 i 维上的坐标值 大于或等于 当前节点的第 i 维坐标值。
构建步骤：
- 输入点集和当前深度。
- 选择分割维度：
split_axis = current_depth % k（例如：深度 0 用维 0(x)，深度 1 用维 1(y)）。 - 按
split_axis维度对点集排序。 - 找到中位数点作为当前节点。
- 创建节点：
point=中位数,axis=split_axis。 - 根据中位数点的值将点集分为左子集和右子集。
- 递归构建左子树和右子树。
- 将左子树赋给当前节点的
.left，右子树赋给.right。 - 返回当前节点。
2.3 构建算法示例
以 2D 为例，点集：[(2,3), (5,4), (9,6), (4,7), (8,1), (7,2)]
构建一个高效的 KD-Tree 的关键在于如何选择分割维度和分割点。常见的方法是：
- 分割维度的选择：循环交替地使用各个维度，例如，根节点用第 0 维（x 轴），下一层用第 1 维（y 轴），再下一层又用回第 0 维，以此类推。
- 分割点的选择：通常选择当前维度下所有点的中位数作为分割点，可以保证构建出来的树是平衡的，搜索效率最高。
构建步骤示例：
-
根节点 (深度=0，使用 x 维)：
- 所有点：
(2,3), (5,4), (9,6), (4,7), (8,1), (7,2) - 按 x 坐标排序：
(2,3), (4,7), (5,4), (7,2), (8,1), (9,6) - 中位数是
(7,2)（如果偶数个点，通常取中间偏右或偏左均可）。
- 所有点：
