到这里位置，上边都是抄的别人的，下边是自己的一点总结。

kd树的创建是一个递归的过程：

開始：确定切分域，这个格局你的特征向量一共同拥有多少维，假如是一个N维向量，而且有M个这种向量。那么你须要计算每个维上边的方差。选取方差大的那个维作为切分域。方差的计算公式。

然后，对依靠这个维上边的值对向量进行升序排序。

选取这个维上边的中位数作为根节点。讲空间切分为两部分，左边和后边的空间域，递归的对两个空间域进行切分。分别增加到二叉树的左右两个孩子节点。

k-d树上的最邻近查找算法

在k-d树中进行数据的查找也是特征匹配的重要环节。其目的是检索在k-d树中与查询点距离近期的数据点。

这里先以一个简单的实例来描写叙述最邻近查找的基本思路。

　　星号表示要查询的点（2.1,3.1）。

通过二叉搜索。顺着搜索路径非常快就能找到最邻近的近似点，也就是叶子节点（2,3）。而找到的叶子节点并不一定就是最邻近的，最邻近肯定距离查询点更近，应该位于以查询点为圆心且通过叶子节点的圆域内。为了找到真正的近期邻，还须要进行‘回溯‘操作：算法沿搜索路径反向查找是否有距离查询点更近的数据点。此例中先从（7,2）点開始进行二叉查找。然后到达（5,4）。最后到达（2,3），此时搜索路径中的节点为<（7,2），（5,4），（2,3）>。首先以（2,3）作为当前近期邻点。计算其到查询点（2.1,3.1）的距离为0.1414，然后回溯到其父节点（5,4），并推断在该父节点的其它子节点空间中是否有距离查询点更近的数据点。以（2.1,3.1）为圆心，以0.1414为半径画圆，如图4所看到的。

发现该圆并不和超平面y = 4交割。因此不用进入（5,4）节点右子空间中去搜索。

再回溯到（7,2），以（2.1,3.1）为圆心。以0.1414为半径的圆更不会与x = 7超平面交割，因此不用进入（7,2）右子空间进行查找。

至此，搜索路径中的节点已经所有回溯完，结束整个搜索。返回近期邻点（2,3）。近期距离为0.1414。

　　一个复杂点了样例如查找点为（2。4.5）。

相同先进行二叉查找。先从（7,2）查找到（5,4）节点，在进行查找时是由y = 4为切割超平面的。因为查找点为y值为4.5。因此进入右子空间查找到（4,7）。形成搜索路径<（7,2），（5,4），（4,7）>。取（4,7）为当前近期邻点，计算其与目标查找点的距离为3.202。然后回溯到（5,4），计算其与查找点之间的距离为3.041。

以（2。4.5）为圆心。以3.041为半径作圆，如图5所看到的。

可见该圆和y = 4超平面交割，所以须要进入（5,4）左子空间进行查找。此时需将（2,3）节点增加搜索路径中得<（7,2），（2,3）>。

回溯至（2,3）叶子节点。（2,3）距离（2,4.5）比（5,4）要近，所以近期邻点更新为（2，3），近期距离更新为1.5。回溯至（7,2）。以（2,4.5）为圆心1.5为半径作圆。并不和x = 7切割超平面交割，如图6所看到的。至此。搜索路径回溯完。返回近期邻点（2,3），近期距离1.5。

k-d树查询算法的伪代码如表3所看到的。

上述两次实例表明，当查询点的邻域与切割超平面两側空间交割时，须要查找还有一側子空间。导致检索过程复杂，效率下降。研究表明N个节点的K维k-d树搜索过程时间复杂度为：t_worst=O（kN^1-1/k）。

我这里对kd树的搜索过程中的回溯推断是否当查询点的邻域与切割超平面两側空间交割时。当向量不是二维而是多维的情况。这里应该是一个球，须要对其他各个维都要计算，假设有一个相切或者相交，那么就必须搜索查询点的右孩子。