共计 1138 个字符，预计需要花费 3 分钟才能阅读完成。
kd 树的结构
kd树是一个二叉树结构，它的每一个节点记载了【特征坐标，切分轴，指向左枝的指针，指向右枝的指针】。
其中，特征坐标是线性空间\(R^n\)中的一个点\(x_1,x_2,…,x_n\)。
切分轴由一个整数\(r\)表示，这里\(1 \le r \le n \)，是我们在 n 维空间中沿第 r 维进行一次分割。
节点的左枝和右枝分别都是 kd 树，并且满足：如果 y 是左枝的一个特征坐标，那么\(y_r \le x_r \)并且如果 z 是右枝的一个特征坐标，那么\(z_r \ge x_r \)。
给定一个数据样本集 \(S \subseteq R^n\)和切分轴 r , 以下递归算法将构建一个基于该数据集的 kd 树，每一次循环制作一个节点：
−− 如果 \(|S|=1\)，记录 S 中唯一的一个点为当前节点的特征数据，并且不设左枝和右枝.\(|S|\) 指集合 S 中元素的数量）
−− 如果\(|S| >1\)：
∙∙ 将 S 内所有点按照第 r 个坐标的大小进行排序；
∙∙ 选出该排列后的中位元素（如果一共有偶数个元素，则选择中位左边或右边的元素，左或右并无影响），作为当前节点的特征坐标，并且记录切分轴 r；
∙∙ 将 \(S_L\) 设为在 S 中所有排列在中位元素之前的元素； \(S_R\) 设为在 S 中所有排列在中位元素后的元素；
∙∙ 当前节点的左枝设为以 \(S_L\) 为数据集并且 r 为切分轴制作出的 kd 树；当前节点的右枝设为以 \(S_R\) 为数据集并且 r 为切分轴制作出的 kd 树。再设\(r\leftarrow(r+1)\ mod\ n \)。（这里，我们想轮流沿着每一个维度进行分割；\(mod\ n \) 是因为一共有 n 个维度，在沿着最后一个维度进行分割之后再重新回到第一个维度。）
构造 kd 树的例子
上面抽象的定义和算法确实是很不好理解，举一个例子会清楚很多。首先随机在 \(\mathbb{R}^2 \) 中随机生成 13 个点作为我们的数据集。起始的切分轴\(r=0\)；这里 \(r=0\)对应 xx 轴，而\( r=1\) 对应 y 轴。
对应 y 轴，左右两边再按照 y 轴的排序进行切分，中位点记载于左右枝的节点。得到下面的树，左边的 x 是指这该层的节点都是沿 x 轴进行分割的。
转载https://zhuanlan.zhihu.com/p/23966698
