定义
KD树(KDT , k-Dimension Tree) 是一种可以高效处理K维空间信息的数据结构。KD树具有二叉搜索树的形态，二叉搜索树上的每个结点都对应K维空间内的一个点[1] 。
相对二叉树而言，二叉树是针对输入数组是一维的情况，如果将一维数组推广到K维情况，那么久得到了KD树。
举例
以二维数组进行举例[2]：
数组B=[[6, 2], [6, 3], [3, 5], [5, 0], [1, 2], [4, 9], [8, 1]]，对于元素x，我们要找到数组B中距离x最近的元素，令x = [1, 1]
KD树的建立：
1、首先找到变化较大的那个维度，由于std(B) = [2.11, 2.79]，所以选择维度2；
2、对于维度2上的数组进行排序，得到[0, 1, 2, 2, 3, 5, 9]，中位数是2，选择[6,2]作为根节点；
3、对于[6,2]左右两侧的节点再分别执行操作1操作2和操作3，直到树完成建立。
图 1 建立得到的KD数
KD树的查找：
1、从根节点[6,2]开始，计算x和根节点之间的距离L1；
2、根据x在维度2中是否小于或大于当前节点，向左或向右移动；
3、计算x和[8,1]之间的距离L2，比较L2和L1的距离，记录最优Lmin；
4、计算x和[5,0]之间的距离L3，比较L3和Lmin的距离，记录最优Lmin；
5、计算x和[1,2]之间的距离L4，比较L3和Lmin的距离，记录最优Lmin。
Lmin对应的那个节点就是x最接近的元素。
参考文献
[1] https://oi-wiki.org/ds/kdt/
[2] https://zhuanlan.zhihu.com/p/45346117
