kd-tree

k-d树是一个二叉树，每个节点表示一个空间范围。表1给出的是k-d树每个节点中主要包含的数据结构。

表1 k-d树中每个节点的数据类型

从上面对k-d树节点的数据类型的描述可以看出构建k-d树是一个逐级展开的递归过程。表2给出的是构建k-d树的伪码。

表2 构建k-d树的伪码

以上述举的实例来看，过程如下:

由于此例简单，数据维度只有2维，所以可以简单地给x，y两个方向轴编号为0,1，也即split={0,1}。

(1)确定split域的首先该取的值。分别计算x，y方向上数据的方差得知x方向上的方差最大，所以split域值首先取0，也就是x轴方向;

(2)确定Node-data的域值。根据x轴方向的值2,5,9,4,8,7排序选出中值为7，所以Node-data = (7,2)。这样，该节点的分割超平面就是通过(7,2)并垂直于split = 0(x轴)的直线x = 7;

(3)确定左子空间和右子空间。分割超平面x = 7将整个空间分为两部分，如图2所示。x < = 7的部分为左子空间，包含3个节点{(2,3)，(5,4)，(4,7)};另一部分为右子空间，包含2个节点{(9,6)，(8,1)}。

如算法所述，k-d树的构建是一个递归的过程。然后对左子空间和右子空间内的数据重复根节点的过程就可以得到下一级子节点(5,4)和(9,6)(也就是左右子空间的'根'节点)，同时将空间和数据集进一步细分。如此反复直到空间中只包含一个数据点，如图1所示。最后生成的k-d树如图3所示。

在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树查询算法的伪代码如下所示。

先以一个简单直观的实例来介绍k-d树算法。假设有6个二维数据点{(2,3)，(5,4)，(9,6)，(4,7)，(8,1)，(7,2)}，数据点位于二维空间内(如图1中黑点所示)。k-d树算法就是要确定图1中这些分割空间的分割线(多维空间即为分割平面，一般为超平面)。下面就要通过一步步展示k-d树是如何确定这些分割线的。

k-d树算法可以分为两大部分，一部分是有关k-d树本身这种数据结构建立的算法，另一部分是在建立的k-d树上如何进行最邻近查找的算法。