KD-Tree

简介

KD-Tree 用来组织表示K维空间点集合。这是一种带有约束条件的二分查找树，KD树对于邻域搜索十分有用。KD-Tree 在除了叶子结点外，每一维分裂都是在某一个维度进行分裂。

 

 

建树算法流程

KD-Node

• value
• split，分裂维度编号
• left，KD-Node left
• right，KD-Node right

 

流程：

1. 确定split分割维度。计算该数据集在每个分割维度的方差，挑选最大的，表示分割的比较好
2. 确定Node-Data，该维度的值进行排序，选择中位数。
3. 确定左、右子空间。左子空间 <= node.value, 右子空间 > node.value

 

查找算法：

流程：

1. 从root出发，DFS搜索直到叶子节点，同时在stack中存储顺序访问的节点
2. 如果搜索到叶子结点，则设为最邻进
3. 然后通过stack回溯，如果当前点的距离比邻近点近，则更新最邻近点，然后检查最近的点到目标点的距离为圆是否和父结点的面相交，如果相交则搜索父节点的另一侧。如果不相交则继续回溯。
4. 直到root

 

参考

https://blog.csdn.net/qq_33287871/article/details/107332728/

https://baike.baidu.com/item/kd-tree/2302515