KD 树(k-d Tree)

定义

KD 树(k-dimensional tree)由 Jon Bentley 于 1975 年提出,是一种对 k 维空间中的点集进行组织的二叉搜索树:每一层按某个维度的坐标把点集一分为二,维度通常轮换选取,分割点常取中位数以保持平衡。

原理

查询最近邻时,先沿树下行到目标点所在叶子得到候选,再回溯:若某分割超平面到目标点的距离小于当前最优距离,则需要进入另一侧子树继续搜索,否则可以整棵剪枝。范围查询同理按分割面判断子树是否可能包含结果。

应用

KD 树广泛用于 k 近邻(kNN)分类、点云配准(如 ICP 算法)、光线追踪加速、地理位置检索等;scikit-learn、PCL、FLANN 等库均内置实现。

优缺点

低维(一般不超过 20 维)时性能优秀;高维空间中因维度灾难退化接近线性扫描,此时常改用近似最近邻结构(如 HNSW、LSH)。动态插入删除也会破坏平衡,需定期重建。