时间：2020-11-17 00:49:54 | 栏目：.NET代码 | 点击：次
本文首先介绍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. 源码交流