K-维树（K-d Tree）的构建与查询
字数 2371 2025-11-13 13:24:18
K-维树（K-d Tree）的构建与查询
K-维树（K-d Tree）是一种用于组织K维空间中点数据的数据结构。它是二叉搜索树在多维空间中的扩展。K-d树常用于范围搜索、最近邻搜索等应用。
1. 基本概念
- K-d树中的每个节点代表一个K维空间中的点。
- 树的每一层都根据一个特定的维度（我们称之为“分割维度”）来对数据进行划分。
- 一个简单的规则是，树的根节点在第0层，使用第0维进行划分；下一层（第1层）使用第1维；以此类推。当深度超过了维度数量（K）时，再回到第0维，循环往复。
2. K-d树的构建过程
构建K-d树的核心是一个递归过程。假设我们要为点集 {(2,3), (5,4), (9,6), (4,7), (8,1), (7,2)} 构建一个2-d树。
-
步骤1：选择根节点
- 当前点集为所有点：
[(2,3), (5,4), (9,6), (4,7), (8,1), (7,2)]。 - 当前分割维度是第0维（x轴）。
- 为了构建一棵平衡的树，我们选择当前维度上的中位数作为分割点。将点集按x坐标排序：
(2,3), (4,7), (5,4), (7,2), (8,1), (9,6)。中位数是(7,2)（如果点数为偶数，通常选择中间两个中的任意一个，这里选(7,2)）。 - 根节点被确定为
(7,2)。分割超平面是垂直于x轴的直线x = 7。
- 当前点集为所有点：
-
步骤2：递归构建左子树
- 左子树包含所有x坐标小于7的点：
[(2,3), (5,4), (4,7)]。 - 现在进入下一层，分割维度变为第1维（y轴）。
- 将左子树的点按y坐标排序：
(2,3), (5,4), (4,7)。中位数是(5,4)。 - 根节点
(7,2)的左子节点是(5,4)。分割超平面是垂直于y轴的直线y = 4。
- 左子树包含所有x坐标小于7的点：
-
步骤3：递归构建右子树
- 右子树包含所有x坐标大于7的点：
[(9,6), (8,1)]。 - 分割维度是第1维（y轴）。
- 将右子树的点按y坐标排序：
(8,1), (9,6)。中位数是(9,6)。 - 根节点
(7,2)的右子节点是(9,6)。分割超平面是垂直于y轴的直线y = 6。
- 右子树包含所有x坐标大于7的点：
-
步骤4：继续递归
- 对于节点
(5,4)的左子树：包含y坐标小于4的点[(2,3)]。分割维度回到第0维。这个点成为(5,4)的左子节点。 - 对于节点
(5,4)的右子树：包含y坐标大于4的点[(4,7)]。分割维度是第0维。这个点成为(5,4)的右子节点。 - 对于节点
(9,6)的左子树：包含y坐标小于6的点[(8,1)]。分割维度回到第0维。这个点成为(9,6)的左子节点。 - 对于节点
(9,6)的右子树：没有y坐标大于6的点，所以为空。
- 对于节点
最终构建出的K-d树结构如下图所示（文本描述）：
(7,2)
/ \
(5,4) (9,6)
/ \ /
(2,3) (4,7) (8,1)
3. K-d树的查询过程：范围搜索
范围搜索的目标是找出所有位于给定轴对齐矩形（或称“超矩形”）内的点。例如，在上面的树中搜索范围 [3,8] (x轴) * [2,6] (y轴)。
-
步骤1：从根节点
(7,2)开始- 检查根节点
(7,2)是否在范围内。x=7在[3,8]内，y=2在[2,6]内，所以点(7,2)是结果之一。 - 由于分割维度是x轴，分割值是7。我们的查询范围在x轴上是[3,8]。
- 因为查询范围的左边界3 < 7，所以必须搜索左子树（
(5,4)及其子树）。 - 因为查询范围的右边界8 > 7，所以必须搜索右子树（
(9,6)及其子树）。
- 检查根节点
-
步骤2：搜索左子树（以
(5,4)为根）- 检查节点
(5,4)。x=5在[3,8]内，y=4在[2,6]内，所以点(5,4)是结果之一。 - 现在分割维度是y轴，分割值是4。查询范围在y轴上是[2,6]。
- 因为查询范围的下边界2 < 4，所以必须搜索左子树（
(2,3)）。 - 因为查询范围的上边界6 > 4，所以必须搜索右子树（
(4,7)）。
- 检查节点
-
步骤3：搜索
(5,4)的左子树（(2,3)）- 检查节点
(2,3)。x=2不在[3,8]内。所以这个点不在范围内，跳过。 - 这是一个叶子节点，返回。
- 检查节点
-
步骤4：搜索
(5,4)的右子树（(4,7)）- 检查节点
(4,7)。x=4在[3,8]内，但y=7不在[2,6]内。所以这个点不在范围内，跳过。 - 这是一个叶子节点，返回。
- 检查节点
-
步骤5：搜索右子树（以
(9,6)为根）- 检查节点
(9,6)。x=9不在[3,8]内。所以这个点不在范围内，跳过。 - 现在分割维度是y轴，分割值是6。查询范围在y轴上是[2,6]。
- 因为查询范围的下边界2 < 6，所以必须搜索左子树（
(8,1)）。 - 查询范围的上边界6等于分割值6。对于轴对齐范围搜索，通常约定如果点的坐标等于边界值，它被包含在内。但这里
(9,6)的x坐标已经超了。对于子树，因为上边界6不小于分割值6，我们通常也需要检查右子树，但此节点没有右子树。
- 检查节点
-
步骤6：搜索
(9,6)的左子树（(8,1)）- 检查节点
(8,1)。x=8在[3,8]内，y=1不在[2,6]内。所以这个点不在范围内，跳过。
- 检查节点
-
最终结果：搜索完成，找到的点是
[(7,2), (5,4)]。
核心思想：在每一步，我们根据当前节点的分割维度和分割值，决定需要递归搜索哪些子树。如果查询范围完全在分割超平面的一侧，则可以剪枝（跳过）另一侧的子树，这大大提高了搜索效率。平均情况下，范围搜索的时间复杂度为O(K * N^(1-1/K))，其中K是维度，N是点数。当K不大时，这比暴力扫描所有N个点要快得多。