本文首先介绍kd-tree的构造方法,然后介绍kd-tree的搜索流程及代码实现,最后给出本人利用c#语言实现的二维kd树代码。这也是我自己动手实现的第一个树形的数据结构。理解上难免会有偏差,敬请各位多多斧正。
1. kd树介绍
kd-tree(kd树),即k-dimensional tree,是一种高维索引树形数据结构,常用于在大规模的高维数据空间进行最邻近查找和近似最邻近查找。我实现的kd树是二维的kd - tree。目的是在点集中寻找最近点。参考资料是kd-tree的百度百科。并且根据百度百科的逻辑组织了代码。
2. kd树的数学解释
3. kd树的构造方法
这里是用的二维点集进行构造kd-tree。三维的与此类似。
树中每个节点的数据类型:
public class kdtreenode { /// <summary> /// 分裂点 /// </summary> public point divisionpoint { get; set; } /// <summary> /// 分裂类型 /// </summary> public enumdivisiontype divisiontype { get; set; } /// <summary> /// 左子节点 /// </summary> public kdtreenode leftchild { get; set; } /// <summary> /// 右子节点 /// </summary> public kdtreenode rightchild { get; set; } }
3.1 kd树构造逻辑流程
3.2 代码实现
private kdtreenode createtreenode(list<point> pointlist) { if (pointlist.count > 0) { // 计算方差 double xobtainvariance = obtainvariance(createxlist(pointlist)); double yobtainvariance = obtainvariance(createylist(pointlist)); // 根据方差确定分裂维度 enumdivisiontype divisiontype = sortlistbyxoryvariances(xobtainvariance, yobtainvariance, ref pointlist); // 获得中位数 point medianpoint = obtainmedian(pointlist); int medianindex = pointlist.count / 2; // 构建节点 kdtreenode treenode = new kdtreenode() { divisionpoint = medianpoint, divisiontype = divisiontype, leftchild = createtreenode(pointlist.take(medianindex).tolist()), rightchild = createtreenode(pointlist.skip(medianindex + 1).tolist()) }; return treenode; } else { return null; } }
4. kd树搜索方法
kd-tree的总体搜索流程先根据普通的查找找到一个最近的叶子节点。但是这个叶子节点不一定是最近的点。再进行回溯的操作找到最近点。
4.1 kd树搜索逻辑流程
4.2 代码实现
public point findnearest(point searchpoint) { // 按照查找方式寻找最近点 point nearestpoint = dfssearch(this.rootnode, searchpoint); // 进行回溯 return backtrcaksearch(searchpoint, nearestpoint); } private point dfssearch(kdtreenode node,point searchpoint,bool pushstack = true) { if(pushstack == true) { // 利用堆栈记录查询的路径,由于树节点中没有记载父节点的原因 backtrackstack.push(node); } if (node.divisiontype == enumdivisiontype.x) { return dfsxsearch(node,searchpoint); } else { return dfsysearch(node, searchpoint); } } private point backtrcaksearch(point searchpoint,point nearestpoint) { // 如果记录路径的堆栈为空则表示已经回溯到根节点,则查到的最近点就是真正的最近点 if (backtrackstack.isempty()) { return nearestpoint; } else { kdtreenode tracknode = backtrackstack.pop(); // 分别求回溯点与最近点距查找点的距离 double backtrackdistance = obtaindistanfromtwopoint(searchpoint, tracknode.divisionpoint); double nearestpointdistance = obtaindistanfromtwopoint(searchpoint, nearestpoint); if (backtrackdistance < nearestpointdistance) { // 深拷贝节点的目的是为了避免损坏树 kdtreenode searchnode = new kdtreenode() { divisionpoint = tracknode.divisionpoint, divisiontype = tracknode.divisiontype, leftchild = tracknode.leftchild, rightchild = tracknode.rightchild }; nearestpoint = dfsbacktrackingsearch(searchnode, searchpoint); } // 递归到根节点 return backtrcaksearch(searchpoint, nearestpoint); } }
5. 源码交流
https://github.com/creammilk/c-kd-tree
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持移动技术网。
如对本文有疑问, 点击进行留言回复!!
使用Visual Studio2019创建C#项目(窗体应用程序、控制台应用程序、Web应用程序)
C#实现获取本地内网(局域网)和外网(公网)IP地址的方法分析
网友评论