介绍KdTree算法

入门，学习KdTree:

   今天因为要看一些代码，所以自己从网上搜了下kdtree得相关内容，今天介绍一下啥是kdtree。

   首先，这是一种分割k维数据空间的数据结构，目的是能够快速查找某个数据，是一种带有约束得二分查找树，能起到一种加速作用。首先插上这张图，一张我看了n多博客都用的经典图：

此图借鉴于右下角得博客，侵权即删。

在此处用最简单得二维数据来介绍，其余同。

假设有6个二维数据点{（2,3），（5,4），（9,6），（4,7），（8,1），（7,2）}，数据点 位于二维空间内（如图1中黑点所示）。k-d树算法就是要确定图1中这些分割空间的分割线（多维空间即为分割平面，一般为超平面）。

由于此例简单，数据维度只有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，所以此点得数据值为（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）}。

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

以上n行借鉴于博客https://www.cnblogs.com/li-yao7758258/p/6437440.html，感谢。

然后介绍一下，我不懂得地方，右边只有俩，那如何看中位数，来确定如何截取呢？翻阅书后，得出，最高效的方法是，将指定维度得值放在根上，小于指定值得数据放于左边，大于的放在右边，然后重复此过程。

所以此过程总的来说，是根据方差和中位数找到（7，2）这个点，然后左边那三放在一坨，右边那俩放一坨。然后左边那三根据方差和中位数再挑出一个（5，4）放于次根，左边的剩下那俩就甭分了，一左一右。

然后再看右边那俩，根据方差后，y轴较大，然后根据大的在右边，所以在为双数时，大的数中挑大的，放右次根，然后两个中较小的放左边，只能放于次根得下面左侧。

接下来就是查询的操作。基本的思路很简单：首先通过二叉树搜索（比较待查询节点和分裂节点的分裂维的值，小于等于就进入左子树分支，等于就进入右子树分支直到叶子结点），顺着“搜索路径”很快能找到最近邻的近似点，也就是与待查询点处于同一个子空间的叶子结点；然后再回溯搜索路径，并判断搜索路径上的结点的其他子结点空间中是否可能有距离查询点更近的数据点，如果有可能，则需要跳到其他子结点空间中去搜索（将其他子结点加入到搜索路径）。重复这个过程直到搜索路径为空。

此例中先从（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为半径画圆，如下图所示。发现该圆并不和超平面y = 4交割，因此不用进入（5,4）节点右子空间中去搜索。

以上参考自https://www.cnblogs.com/li-yao7758258/p/6437440.html，

https://blog.csdn.net/silangquan/article/details/41483689，

感谢，具体代码函数说明直接见上，写这篇blog来提醒自己。