KD树¶

概述¶

KD树（K-Dimensional Tree）是一种空间划分数据结构，用于组织K维空间中的点。通过交替选择不同维度进行划分，将空间递归分割成超矩形区域，支持高效的范围搜索和最近邻搜索。

核心思想：每一层选择一个维度进行划分，将空间分成两部分。对于2D空间，第一层按X轴划分，第二层按Y轴划分，第三层再按X轴划分，以此类推。

KD树特点¶

特性	说明
多维索引	支持任意维度空间
二叉树结构	每个节点划分一个维度
交替分割	不同层使用不同维度分割
高效查询	最近邻查询平均 O(log n)
空间划分	每个节点对应一个超矩形区域

KD树结构可视化¶

2D KD树构建过程¶

点集：{(2,3), (5,4), (9,6), (4,7), (8,1), (7,2)}

第1层（按X轴划分）：

点集按X排序: (2,3), (4,7), (5,4), (7,2), (8,1), (9,6)

中位数: (7,2)

完整KD树：

graph TB
    subgraph KD树结构
        n1(("7,2<br/>X轴分割"))
        n2(("5,4<br/>Y轴分割"))
        n3(("9,6<br/>Y轴分割"))
        n4(("2,3"))
        n5(("4,7"))
        n6(("8,1"))
        
        n1 --> n2 --> n4
        n2 --> n5
        n1 --> n3 --> n6
    end
    
    style n1 fill:#4CAF50,color:#fff
    style n2 fill:#2196F3,color:#fff
    style n3 fill:#2196F3,color:#fff
    style n4 fill:#FF9800,color:#fff
    style n5 fill:#FF9800,color:#fff
    style n6 fill:#FF9800,color:#fff

空间划分可视化¶

空间划分过程

原始空间

第1层分割（X=7）

第2层分割（左Y=4, 右Y=6）

划分规则：第 d 层使用维度 d % K 进行划分。对于2D树，奇数层用X轴，偶数层用Y轴。

数据结构定义¶

C
#define MAX_DIM 3

typedef struct {
    double coords[MAX_DIM];
} Point;

typedef struct KDNode {
    Point point;              // 该节点存储的点
    int splitDim;             // 分割维度
    struct KDNode *left;      // 左子树
    struct KDNode *right;     // 右子树
} KDNode;

typedef struct {
    KDNode *root;
    int dim;
} KDTree;

创建KD树¶

节点创建¶

C
KDNode* createKDNode(Point point, int splitDim) {
    KDNode *node = (KDNode*)malloc(sizeof(KDNode));
    node->point = point;
    node->splitDim = splitDim;
    node->left = NULL;
    node->right = NULL;
    return node;
}

KDTree* createKDTree(int dim) {
    KDTree *tree = (KDTree*)malloc(sizeof(KDTree));
    tree->root = NULL;
    tree->dim = dim;
    return tree;
}

构建KD树¶

C
int comparePoints(const void *a, const void *b, int dim) {
    Point *pa = (Point*)a;
    Point *pb = (Point*)b;
    if (pa->coords[dim] < pb->coords[dim]) return -1;
    if (pa->coords[dim] > pb->coords[dim]) return 1;
    return 0;
}

KDNode* buildKDTree(Point points[], int n, int depth, int k) {
    if (n <= 0) return NULL;
    
    // 选择分割维度
    int axis = depth % k;
    
    // 按当前维度排序
    // 这里需要自定义比较函数
    qsort(points, n, sizeof(Point), /* 比较函数 */);
    
    // 选择中位数作为当前节点
    int mid = n / 2;
    
    KDNode *node = createKDNode(points[mid], axis);
    
    // 递归构建左右子树
    node->left = buildKDTree(points, mid, depth + 1, k);
    node->right = buildKDTree(points + mid + 1, n - mid - 1, depth + 1, k);
    
    return node;
}

构建过程示意¶

flowchart TD
    A["点集P, 深度d"]
    B["选择分割维度<br/>axis = d % K"]
    C["按axis排序"]
    D["选择中位数作为节点"]
    E["构建左子树<br/>点集 = 左半部分"]
    F["构建右子树<br/>点集 = 右半部分"]
    G["返回节点"]
    
    A --> B --> C --> D --> E --> F --> G
    
    style A fill:#E3F2FD
    style D fill:#4CAF50,color:#fff
    style G fill:#E8F5E9

插入操作¶

C
KDNode* insertKD(KDNode *root, Point point, int depth, int k) {
    // 空节点，创建新节点
    if (root == NULL) {
        return createKDNode(point, depth % k);
    }
    
    // 确定分割维度
    int axis = root->splitDim;
    
    // 根据当前维度决定插入左子树还是右子树
    if (point.coords[axis] < root->point.coords[axis]) {
        root->left = insertKD(root->left, point, depth + 1, k);
    } else {
        root->right = insertKD(root->right, point, depth + 1, k);
    }
    
    return root;
}

void insert(KDTree *tree, Point point) {
    tree->root = insertKD(tree->root, point, 0, tree->dim);
}

插入示例：

KD树插入点 (6,5)

插入前

→

插入后

路径: (7,2) → X≥7 → (9,6) → Y≤6 → (8,1) → X≤8 → 插入(6,5)

最坏情况：当所有点都在一条线上时，KD树退化为链表，查询复杂度变为 O(n)。

空间复杂度¶

树节点：O(n)
递归栈：O(log n) 平均，O(n) 最坏

应用场景¶

应用领域	具体场景
机器学习	K近邻算法（KNN）
空间数据库	多维索引查询
图像处理	特征点匹配
计算机视觉	点云配准
计算几何	最近点对问题
游戏开发	碰撞检测

KD树 vs 其他空间索引¶

索引结构	最近邻	范围查询	动态更新	高维性能
KD树	O(log n)	良好	困难	较差
R树	O(log n)	良好	容易	较好
四叉树	O(log n)	良好	容易	仅限低维
网格索引	O(1)	良好	容易	空间爆炸

选择建议：静态数据且维度较低（≤20）时，KD树是最近邻搜索的最佳选择。动态更新频繁或高维数据，考虑R树或近似最近邻算法。

实际应用示例¶

点云最近邻搜索¶

C++
// 3D点云最近邻
KDTree<3> tree;
// ... 构建树

std::array<double, 3> query = {x, y, z};
auto nearest = tree.findNearest(query);

K近邻搜索（KNN）¶

C++
template<int K, int Dim>
std::vector<std::array<double, Dim>> kNearest(
    KDTree<Dim>& tree, 
    const std::array<double, Dim>& target, 
    int k) {
    // 使用优先队列维护K个最近邻
    std::priority_queue<std::pair<double, std::array<double, Dim>>> pq;
    // ... 实现
    return results;
}

参考资料¶

Bentley, J. L. (1975). Multidimensional Binary Search Trees Used for Associative Searching
Friedman, J. H. et al. (1977). An Algorithm for Finding Best Matches in Logarithmic Expected Time
《计算几何：算法与应用》

变体	特点	适用场景
2D树	二维空间划分	图像处理、计算几何
3D树	三维空间划分	点云处理、3D图形
KD-B树	结合B树，减少树高度	大规模数据
BKD树	批量构建KD树	只读数据集

KD树¶

概述¶

KD树特点¶

KD树结构可视化¶

2D KD树构建过程¶

空间划分可视化¶

数据结构定义¶

创建KD树¶

节点创建¶

构建KD树¶

构建过程示意¶

插入操作¶

最近邻搜索¶

距离计算¶

最近邻搜索算法¶

最近邻搜索示意¶

范围搜索¶

C++ 实现¶

KD树变体¶

时间复杂度¶