Have a Question?
K-D 树 | K Dimensional Tree
1 定义
在计算机科学里，K-D 树（ k-维树的缩写）是在k维欧几里德空间组织点的数据结构。k-d树可以使用在多种应用场合，如多维键值搜索（例：范围搜寻及最邻近搜索）。k-d树是空间二分树（Binary space partitioning）的一种特殊情况。K-D 树中的特征是 n 维向量：\(\{x_1, x_2, \cdots, x_n\}\)。
K-D 树通常记录了如下信息：
|
1 2 3 4 5 6 7 8 |
struct kdtree{ Node-data - 数据矢量 数据集中某个数据点，是n维矢量（这里也就是k维） Range - 空间矢量 该节点所代表的空间范围（可选） split - 整数 垂直于分割超平面的方向轴序号 Left - kd树 由位于该节点分割超平面左子空间内所有数据点所构成的k-d树 Right - kd树 由位于该节点分割超平面右子空间内所有数据点所构成的k-d树 parent - kd树 父节点（可选） } |
2 创建
以一个二维点云创建过程举例：假设我们要处理的二维 \((x, y)\) 点云集合为：\((30,40), (5,25), (10,12), (70,70), (50,30), (35,45)\)。
1）按照 x 维进行划分，找到中位数节点 \((30,40)\)，x 坐标比 30 小的放入左子树集合 \((5,25), (10,12)\)，大的放入右子树集合 \((70,70), (50,30), (35,45)\)。
2）对左右子树集合，按照 y 维度进行划分：
左子树集合，中位数节点为 \((5,25)\)，然后重复上面的划分步骤。
右子树集合，中位数节点为 \((70,70)\)，然后重复上面的划分步骤。
3）因为只有2个维度，依次迭代 x 和 y 维度即可创建。
划分的步骤示意图如下：
最终建好的 K-D 树如下：
伪代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 |
insert(Point x, KDNode t, int cd) { if t == null t = new KDNode(x) else if (x == t.data) // error! duplicate else if (x[cd] < t.data[cd]) t.left = insert(x, t.left, (cd+1) % DIM) else t.right = insert(x, t.right, (cd+1) % DIM) return t } |
参考文献
[1] https://zh.wikipedia.org/wiki/K-d%E6%A0%91
[2] https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/kdtrees.pdf
[3] https://www.joinquant.com/view/community/detail/c2c41c79657cebf8cd871b44ce4f5d97 (带图文方式详细演示)