首先来一个问题：
给定平面上一个点集 E ，还有一个定点 V ，怎么在一群点中找出一个点 U，使得 V 与 U 的距离最近（欧几里得距离）？
当然，我们能够想到一种做法：枚举 E 中所有的点，找出它们中距离V 最近的点 U。
但是，假设现在有两个点集 E1 与 E2 ，对于 E2 中每一个点 Vi ，找出一个在E1 中的一个点 Ui，使得 Vi 到 Ui 的距离最短，这怎么做？还是枚举？
既然枚举的复杂度很高 ( O(n) 的复杂度 )，那有没有办法把复杂度降下来呢？答案是肯定的，引入一种数据结构：K-D tree
一、何为 K-D tree？
二叉树（有左儿子，右儿子的那种树形结构）
二、能解决哪些问题？
K-D tree 可以在 log(n) （ 最坏是 sqrt(n) ）的时间复杂度内求出一个点集 E 中，距离一个定点 V 最近的点（最近邻查询），稍稍处理一下，我们还可以求出点集 E 中距离距离 V 最近的 k 个点（k邻近查询）
三、怎么利用 K-D tree 解决上面的问题？
将点集 E中的点按照某种规则建成一棵二叉树，查询的时候就在这颗建好的二叉树上面用 log(n) （最坏是 sqrt(n)）的时间复杂度查询出距离最近的点
四、既然是二叉树，怎么建树？
这是最关键的地方，因为不管是 划分树 ， 线段树 ， 字典树 ，甚至是其他的数据结构或者算法（例如 KMP 之类的） ，之所以能够高效的处理问题，主要就是预处理的好。 K-D tree 之所以高效，就是因为建树很高明，高明之处体现在 “将点集 E中的点按照某种规则建成一棵二叉树” 的这种规则上
在讲这种规则之前，我们先来看看 K-D tree 这种数据结构为什么叫做 K-D tree
K：K邻近查询中的k
D：空间是D维空间（Demension）
tree：你可以理解为是二叉树，也可以单纯的看做是一颗 tree
好了， K 我们已经用到了，tree 我们也已经用到了，但是 D 呢？貌似这篇文章到现在为止还没有提到过 D 吧？
这种规则，就是针对空间的“维”的
既然要建树，那么树上的节点肯定要定义一些状态：
节点的状态：
分裂点（split_point）
分裂方式（split_method）
左儿子（left_son）
右儿子（right_son）
我们建树的规则就是节点的状态中的：分裂方式（split_method）
想必读者已经看见上面的关键字了：分裂点 分裂方式，为什么反复的出现分裂这两个字呢？难道建一颗 K-D tree 还要分裂什么，分裂空间？
对，K-D tree的建立就是分裂空间的过程！
怎么建树呢？
建树依据：
先计算当前区间 [ L , R ] 中（这里的区间是点的序号区间，而不是我们实际上的坐标区间），每个点的坐标的每一维度上的方差，取方差最大的那一维，设为 d，作为我们的分裂方式（split_method ），把区间中的点按照在 d 上的大小，从小到大排序，取中间的点 sorted_mid 作为当前节点记录的分裂点，然后，再以 [ L , sorted_mid-1 ] 为左子树建树 ， 以 [sorted_mid+1 , R ] 为右子树建树，这样，当前节点的所有状态我们便确定下来了：
split_point= sorted_mid
split_method= d
left_son = [ L , sorted_mid-1 ]
right_son = [ sorted_mid+1 , R ]
为了便于理解，我先举个例子：
假设现在我们有平面上的点集 E ，其中有 5 个二维平面上的点 ： （1,4）（5,8） （4,2） （7,9） （10，11）
它们在平面上的分布如图：