高级数据结构-05：KD 树

预备知识：Complete BST

定义

KD 树可以视为标准二叉搜索树向多维几何空间的推广。先回顾一维二叉搜索树：对任意内部节点 $v$ ，其键值满足：

$\forall v, v.key = \min\{u.key | u \in v.rTree\} = v.succ.key$

该公式表示：节点 $v$ 的键值等于其右子树（ $rTree$ ）中所有节点键值的最小值，也等于该节点在中序遍历中的直接后继键值。由此可得到二叉搜索树的左右子树约束：

左子树有界： $\forall u \in v.lTree, u.key < v.key$ ；右子树半闭： $\forall u \in v.rTree, u.key \ge v.key$ 。也就是说，左子树中的键都小于当前节点，右子树中的键都大于或等于当前节点。

在这种结构上，search(x) 不只用于寻找精确匹配值，也可返回树中“不大于目标值 $x$ 的最大键值”。这一边界查询能力，是后续进行范围裁剪与空间相交测试的基础。

复杂度分析

操作	复杂度
范围查询	$\mathcal{O}(\log n + k)$	算法查找 LCA 并沿两侧路径下探深度的过程受限于树高 $\mathcal{O}(\log n)$ 。若需将符合条件的子树节点全量枚举，则需附加 $\mathcal{O}(k)$ 的输出代价，其中 $k$ 为实际落入区间的结果总数。
数据预处理	$\mathcal{O}(n \log n)$	采用分治策略构建最优树结构需要对原始数据进行全局排序或重复执行中位数查找。诸如快速排序或归并排序的理论下界决定了预处理过程为 $\mathcal{O}(n \log n)$ 。
结构存储	$\mathcal{O}(n)$	二叉搜索树通过指针直接链接各数据节点，无需构建高维空间下的冗余网格或附加辅助索引。总节点数严格等于数据规模 $n$ ，空间开销较紧凑。

KD 树

Divide-And-Conquer

KD 树引入分治策略：

KD 树从包含整个数据集的初始区域开始构建，即整个平面或多维空间。递归分治步骤如下：

算法按树深度交替选择切分维度。若根位于第 0 层，则偶数层使用第一维（二维平面中的 X 轴）切分，生成垂直分割线，将空间分为左右子区域；奇数层使用第二维（Y 轴）切分，生成水平分割线，将空间分为上下子区域。

算法递归划分每个子区域，直到子区域只包含一个数据点或为空。多维空间因此被转化为嵌套的矩形包围盒。

为了让分治策略在不同数据分布下尽量保持平衡，空间切分算法需要遵循两个约束：

切分均匀性。为了使 KD 树接近平衡，每次切分应尽量把当前区域内的数据点分成规模接近的两部分，使树深保持在 $\mathcal{O}(\log n)$ 。
区域边界开闭性。在连续几何空间中，落在分割线上的点会产生归属歧义。可以规定每个矩形区域左下边界为开区间，右上边界为闭区间，确保任意坐标点只属于唯一叶子节点。

假设存在一个包含 A、B、C、D、E、F、G 共 7 个数据点的二维平面，KD 树的递归切分过程如下：

初始阶段，算法处理整个平面并选择 X 轴。通过线性选择算法，在 X 轴投影中找到中位数对应的垂直分割线 $l_1$ 。平面被分成左右两部分，点 C 作为中位点位于分割线上。

第二阶段，针对 $l_1$ 左侧子空间，算法切换至 Y 轴，寻找 Y 坐标中位数并绘制水平分割线 $l_2$ 。同时，对 $l_1$ 右侧子空间独立计算 Y 坐标中位数，绘制水平分割线 $l_3$ 。至此，平面被切分为四个独立矩形区域。

第三阶段，算法回到 X 轴。对由 $l_2$ 和 $l_3$ 形成的四个子区域分别计算 X 轴中位数，并绘制垂直分割线 $l_4$ 、 $l_5$ 、 $l_6$ 。随着层级加深，算法交替使用垂直线和水平线，直到每个数据点被划入独立小区域。

KD 树的每个节点都同时有两层含义。树结构上，它是一个二叉搜索节点；几何结构上，它代表一次按某个坐标轴进行的空间切分。偶数层按 $x$ 比较，奇数层按 $y$ 比较，本质上是把“多维大小关系”拆成一连串一维判断。读 KD 树算法时，始终追踪“当前节点使用哪一维切分”和“当前子树对应哪块区域”，就不容易迷失。

性能对比：四叉树

KD 树与四叉树都用于空间划分，但切分方法和代价不同。

对比维度	KD 树	四叉树
空间切分	数据驱动。依赖数据点的中位数作为切分基准，自适应于数据的密集程度。	空间驱动。通常选取几何空间的中心点进行强制对等切分，忽略数据分布规律。
维度切分	轴交替。在同一拓扑深度，只对一个维度（水平或垂直）进行一次切分。	同步切分。在每个节点同时使用水平和垂直两条线，将空间直接划分为四个象限（NW, NE, SW, SE）。
节点分支	恒为 2。即使推广到极高维空间，每个节点依然只有两个子分支，指针开销低。	指数级扩展。在二维空间为 4 个分支，在 $d$ 维空间中（如八叉树等）分支数将呈 $2^d$ 暴增。
树高与平衡性	若按中位数构建，可保持接近平衡，树高通常为 $\mathcal{O}(\log n)$ 。	在数据高度偏斜的区域，可能产生大量的空分支节点和较深的嵌套层级。

KD 树在保持二叉结构的同时，通常能更好适应非均匀数据分布。处理维度较高且分布不均的数据时，四叉树更容易出现大量空分支或深层嵌套。

buildKdTree

该函数接收数据点集 $P$ 以及当前的递归深度 $d$ 作为输入参数。伪代码如下：

// 输入 P 为当前子问题的点集，d 为当前递归深度。
buildKdTree(P, d)
// 若点集只包含一个点，则创建叶节点并结束递归。
if ( P == {p} ) return CreateLeaf( p )
// 多点子问题需要创建内部节点保存切分信息。
root = CreateKdNode()
// 偶数深度按 x 方向垂直切分，奇数深度按 y 方向水平切分。
root->splitDirection = Even(d)? VERTICAL : HORIZONTAL
// 在当前切分维度上选取中位数，使左右子问题规模接近平衡。
root->splitLine = FindMedian(root->splitDirection, P)
// 根据切分线把点集拆分为两个子集。
(P1, P2) = Divide(P, root->splitDirection, root->splitLine)
// 递归构建左右子树；深度增加后切分维度切换。
root->lChild = buildKdTree(P1, d + 1)
root->rChild = buildKdTree(P2, d + 1)
// 返回当前子树根节点。
return(root)

算法首先处理递归出口。当子集 $P$ 只包含单个点 {p} 时，递归终止，调用 CreateLeaf(p) 创建叶子节点并返回。若 $P$ 包含多个点，则创建内部节点 CreateKdNode()。随后通过 Even(d)? VERTICAL : HORIZONTAL 根据当前深度 $d$ 的奇偶性确定切分轴。

主要计算瓶颈在 FindMedian。为了保持树接近平衡，算法需要在当前切分轴上找到中位数，并以该坐标建立分割线 splitLine。在未预排序数组中，Median-of-Medians 可保证最坏 $\mathcal{O}(n)$ 选择时间；Quickselect 平均时间为 $\mathcal{O}(n)$ 。确定分割线后，Divide 将切分维度上小于中位数的点划入 $P_1$ ，大于或等于中位数的点划入 $P_2$ 。最后递归构建 $P_1$ 和 $P_2$ ，深度变为 $d+1$ ，并将返回子树挂到 lChild 与 rChild。

设构建包含 $n$ 个数据点的 KD 树总耗时为 $T(n)$ 。在递归的每一层，寻找中位数以及划分两个子集的操作耗时为线性的 $\mathcal{O}(n)$ 。随后，问题被均匀划分为两个规模为 $n/2$ 的子问题进行递归。因此，我们得到标准的递归关系式：

$T(n) = 2T(n/2) + \mathcal{O}(n)$

其解析解为 $T(n) = \mathcal{O}(n \log n)$ 。这说明构建一棵静态、平衡的 KD 树需要 $\mathcal{O}(n \log n)$ 的预处理时间。

以下图为例可以观察集合 {A,B,C,D,E,F,G} 的具体切分过程：

在根节点层（深度 0，垂直切分），依据 X 轴坐标寻找中位数，点 C 被选为切分点。全集 {A,B,C,D,E,F,G} 被划分，其中坐标较小的 {A,B,G} 连同中位点进入左侧子树，坐标较大的 {D,E,F} 进入右侧分支的处理范围。

在深度 1（水平切分），针对左侧子集 {A,B,C,G}，算法切换至 Y 轴，选出点 B 作为新的中位点，将该子集继续划分为上方的 {A,C} 与下方的 {G}，B 点并入下方集合。右侧分支也按 Y 轴坐标对称划分。

范围查询

规范子集

每个节点在几何上对应平面中的一个矩形子区域，并映射被该区域完全包含的数据点子集。这种与节点绑定的点集结构称为规范子集。

规范子集具备以下属性：

对于任何一个树中的内部节点 $X$ ，以及它的左孩子 $L$ 和右孩子 $R$ ，必然成立等式： $region(X) = region(L) \cup region(R)$ 。即父节点的几何区域等价于其左右子节点区域的空间拼接。
所有位于树结构同一深度的节点，其所代表的几何子区域彼此之间互斥，不会产生空间重叠。
若将同一深度的所有内部节点的子区域进行合并，其并集将覆盖整个初始平面空间。

参考前文由分割线 $l_1$ 至 $l_6$ 形成的网格：当矩形查询窗口落在平面上时，它会完全覆盖某些内部节点对应的矩形区域，也会部分穿过另一些区域。被完全覆盖的矩形区域就是查询命中的规范子集。算法可以直接报告这些区域绑定的全部点，避免逐点枚举。

kdSearch

基于规范子集，KD 树的空间范围查找可封装为 kdSearch(v, R)。该算法接收当前节点指针 v 与查询范围对象 R，并通过包含测试、相交测试剪枝。C++ 伪代码和图示如下：

算法先处理递归底层。当指针到达叶子节点（isLeaf(v)）时，退化为坐标比较：调用 inside(v, R) 判断单个数据点是否落入查询范围，若是则 report(v) 输出结果，随后结束当前路径递归。

对于内部节点，算法执行相交测试与子树剪枝。以左子树 v->lc 为例：若其矩形区域被查询区域 $R$ 完全包含，即 $region(v->lc) \subseteq R$ ，则该左子树构成规范子集，算法直接调用 reportSubtree(v->lc) 输出整棵子树，不再深入。若全包含失败，但区域与 $R$ 相交，即 $region(v->lc) \cap R \neq \emptyset$ ，说明目标点可能存在于该子树内，于是递归调用 kdSearch(v->lc, R)。若交集为空，则剪枝该子树。右子树 v->rc 按同样逻辑处理。

范围查询可以按“三分法”：完全包含就整棵输出，完全相离就整棵丢弃，部分相交才递归深入。真正昂贵的是第三种情况，因为查询边界切过了节点区域，算法不得不继续分辨里面哪些点在窗口中。

KD 树二维范围查询的时间复杂度为 $\mathcal{O}(\sqrt{n} + k)$ 。主要开销来自查询矩形 $R$ 边界切过的区域节点。考虑矩形边界的一条垂直线，它会穿过多少内部节点区域？KD 树按层交替切分维度。若根节点垂直切割，两个子节点水平切割，则向下两层后，空间被划分为四个包含 $n/4$ 个数据点的子区域。垂直测试边界最多穿过其中两个子区域。因此，边界线穿过的区域数量 $Q(n)$ 满足：

$Q(n) = 2Q(n/4) + \mathcal{O}(1)$

其解析解为 $Q(n) = \mathcal{O}(n^{\log_4 2}) = \mathcal{O}(n^{1/2}) = \mathcal{O}(\sqrt{n})$ 。矩形 $R$ 有四条边，相交节点总数上限仍为 $\mathcal{O}(\sqrt{n})$ 。再加上通过 reportSubtree 输出 $k$ 个结果节点所需的线性时间，二维范围查询复杂度为 $\mathcal{O}(\sqrt{n} + k)$ 。推广到 $d$ 维时，最坏复杂度为 $\mathcal{O}(n^{1-1/d} + k)$ 。

以下用 A 至 J 的图观察查询过程。算法先评估包含全集 ABCDEFGHIJ 的根节点空间。如果该空间只与目标范围部分重叠，则继续检查子集 ABCGJ 和 DEFHI。

算法先查看左子树的 ABCGJ：

它的左子树划分出的区域 BGJ 与搜索区域明显没有交集，所以可以直接剪枝掉。
它的右子树划分的区域与查询区域相交，于是算法对其中的点分别评估，丢弃掉不在查询范围内的 A，然后将处于查询范围内的 C 输出。

接下来查看右子树划分出的区域 DEFHI：

它的左子树为 EFH，这个区域和查询范围是相交的，所以算法进一步深入查询，发现左子树 FH 完全被查询集合包含，于是直接将这个子树输出，而右子树中的一个点 E 并不在查询范围内并将其丢弃。
右子树 DI 由于也与查询范围相交，于是对其中的两个点分别评估，得出不在查询范围内并丢弃。

Bounding Box

为了高效完成 region(v) ∩ R 相交测试和 region(v) ⊆ R 包含测试，KD 树内部节点通常需要隐式或显式维护边界框。边界框由最小、最大多维坐标向量（Min, Max）表示当前区域范围。执行 kdSearch 时，只需比较查询矩形与节点边界框端点坐标，而不必做复杂多边形碰撞检测，本质上是用额外空间换取执行效率。

最近邻搜索

NN 搜索算法

在数据分布较均匀的低维空间中，NNSearch 的时间复杂度可以接近 $\mathcal{O}(\log n)$ 。该性能依赖超球面构建与回溯剪枝；在高维空间中，剪枝效果可能明显下降。

其核心步骤如下：

第一阶段，算法从 KD 树根节点开始，根据节点层级对应的切分方向（X-Splitting planes 或 Y-Splitting planes）比较目标点坐标与分割面。算法先按贪心策略进入目标点所在的空间分支，直到抵达某个叶子节点。

到达叶子节点后，进入第二阶段。该叶子节点被标记为当前最优估计。算法计算目标点与该叶子节点之间的距离，并以该距离为半径、以目标点为圆心，形成一个虚拟的 N 维超球面。该超球面表示仍可能存在更优解的空间边界。

第三阶段是回溯与相交检查。算法沿原先深度优先下探路径逐级返回父节点。在每个父节点处执行以下逻辑：

首先，检查父节点自身是否落入超球面内，即父节点与目标点的距离是否小于“当前最优估计”。若是，则更新当前最优估计节点，并相应地收缩超球面的半径。
其次，执行跨分支相交测试。在父节点处，除检查节点自身外，还要判断是否需要进入先前跳过的另一侧子树。判定标准是：计算目标点到父节点分割超平面的垂直距离。如果该距离小于当前超球面半径，说明超球面穿过分割面，另一侧子树可能包含更近节点。
此时不能直接剪枝另一侧区域，需要进入该子树并重新执行深度优先与回溯探索。反之，若垂直距离大于或等于当前半径，则另一侧任意节点都不可能优于当前最优估计，可以剪枝并继续向上回溯。

通过动态收缩超球面，并结合法向距离进行剪枝，KD 树在低维、分布较均匀的数据上可以减少逐点距离计算。

最近邻搜索的判断标准简单来说是：先走查询点所在的那一侧，拿到一个当前最好距离；回溯时，如果另一侧区域离查询点的最小可能距离已经不小于当前最好距离，就不可能藏有更优解，可以剪掉。二维图里这个“最小可能距离”常表现为点到分割线或边界框的距离。

算法实现

高维度的回溯容易引发较深的函数调用链，导致栈内存压力或缓存命中率下降。为了提升工程性能，NNS 的实现可以用显式栈管理替代原生函数递归。

数据结构定义如下，除左右子树指针外，还需要显式存储当前节点负责切分的维度：

// KDNode 表示 KD 树中的一个数据点及其左右空间分支。
struct KDNode {
    // 当前节点保存的多维点坐标。
    vector<double> point;
    // 切分面左侧或当前轴坐标较小的一侧子树。
    KDNode* left;
    // 切分面右侧或当前轴坐标较大的一侧子树。
    KDNode* right;
    // 当前节点使用的切分维度下标。
    int axis;
    // 构造节点时写入坐标与切分维度，并将左右孩子初始化为空。
    KDNode(const vector<double>& pt, int a)
        : point(pt), left(nullptr), right(nullptr), axis(a) {}
};

基于栈的搜索可以划分为三个阶段：

第一阶段： 创建用于追踪回溯路径的空指针栈 search_stack。同时设置全局最小距离变量，初始值为系统支持的最大浮点数，并将最近邻节点指针初始化为空。

第二阶段： 算法沿目标点所在路径下探至叶子节点。循环过程中，每个被访问的内部节点都会压入显式栈（search_stack.push(current);）。下探时也可以同步计算当前节点与目标点距离，提前更新最近邻记录。

第三阶段： 探底完成后，开始持续从栈顶弹出节点逆向验证：

// search_stack 保存从根到当前搜索路径上的节点，用于回溯检查另一侧分支。
while (!search_stack.empty()) {
    // 取出最近一次下探路径上的节点。
    KDNode* node = search_stack.top();
    // 弹出后开始处理该节点对应的分割面。
    search_stack.pop();
    // 计算目标点到 node 所在分割面的垂直距离。
    if (需要检查另一侧) {
        // 若垂直距离小于当前最优距离，则另一侧子树可能包含更近点。
        // 对另一侧子树执行深度搜索，并把新路径继续压入 search_stack。
    }
}

在 pop 循环中，算法读取每个 node 的 axis 属性，并用一次一维标量减法得到目标点到该分割面的垂直距离。若该距离绝对值小于当前最近距离，说明当前超球面与父节点分割面相交，另一侧分支可能包含更优解。此时取得另一侧子树根指针，并重新执行第二阶段的下探逻辑，将沿途节点追加至栈中。若垂直距离不小于当前最好距离，则剪枝另一侧空间。栈清空后，缓存节点即为当前搜索得到的最近邻。

复杂度总结

表格展示了 KD 树在处理包含 $n$ 个记录的数据集时，各类操作的时间复杂度表现。动态插入、删除和最近邻查询的复杂度依赖树的平衡性、数据分布和剪枝；若树严重失衡或维度较高，相关操作可能退化。

算法操作类别	理论时间复杂度表现	核心计算逻辑与特性说明
节点插入	平衡树中平均 $\mathcal{O}(\log n)$ ，最坏 $\mathcal{O}(n)$	插入沿树高向下遍历至叶子节点，代价与树高成正比；若不重建或不再平衡，连续偏序插入可能导致树高增加。
根节点删除	典型边界可达 $\mathcal{O}(n^{(k-1)/k})$	删除根节点需要寻找合适的后继节点进行替换，这涉及在多维子树中跨维度寻找最值，代价较普通搜索更高。
随机节点删除	平衡树中平均 $\mathcal{O}(\log n)$ ，最坏 $\mathcal{O}(n)$	对于一般叶子节点或低度数内部节点的删除，结构调整代价较低；但最坏情况下仍受树高与替换节点查找影响。
树结构优化	$\mathcal{O}(n \log n)$	重新构建并优化整棵树的拓扑结构，使后续检索操作更接近平衡树上的性能。
指定键值的偏匹配查询	$\mathcal{O}(n^{(k-t)/k})$	当在 $k$ 维空间中指定 $t$ 个关键字进行查询时，被证明的最大运行时间边界。
最近邻查询	$\mathcal{O}(\log n)$	在数据分布较为均匀的情况下，经验观察得到的平均检索运行时间。