本文首先介紹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
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持武林網。
新聞熱點
疑難解答
