本文首先介紹Kd-Tree的構(gòu)造方法，然后介紹Kd-Tree的搜索流程及代碼實(shí)現(xiàn)，最后給出本人利用C#語(yǔ)言實(shí)現(xiàn)的二維KD樹代碼。這也是我自己動(dòng)手實(shí)現(xiàn)的第一個(gè)樹形的數(shù)據(jù)結(jié)構(gòu)。理解上難免會(huì)有偏差，敬請(qǐng)各位多多斧正。
1. KD樹介紹
Kd-Tree（KD樹），即K-dimensional tree，是一種高維索引樹形數(shù)據(jù)結(jié)構(gòu)，常用于在大規(guī)模的高維數(shù)據(jù)空間進(jìn)行最鄰近查找和近似最鄰近查找。我實(shí)現(xiàn)的KD樹是二維的Kd - tree。目的是在點(diǎn)集中尋找最近點(diǎn)。參考資料是Kd-Tree的百度百科。并且根據(jù)百度百科的邏輯組織了代碼。
2. KD樹的數(shù)學(xué)解釋
3. KD樹的構(gòu)造方法
這里是用的二維點(diǎn)集進(jìn)行構(gòu)造Kd-tree。三維的與此類似。
樹中每個(gè)節(jié)點(diǎn)的數(shù)據(jù)類型：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
public class KDTreeNode { /// <summary> /// 分裂點(diǎn) /// </summary> public Point DivisionPoint { get; set; } /// <summary> /// 分裂類型 /// </summary> public EnumDivisionType DivisionType { get; set; } /// <summary> /// 左子節(jié)點(diǎn) /// </summary> public KDTreeNode LeftChild { get; set; } /// <summary> /// 右子節(jié)點(diǎn) /// </summary> public KDTreeNode RightChild { get; set; } } |
3.1 KD樹構(gòu)造邏輯流程
- 將所有的點(diǎn)放入集合a中
- 對(duì)集合所有點(diǎn)的X坐標(biāo)求得方差xv,Y坐標(biāo)求得方差yv
- 如果xv > yv,則對(duì)集合a根據(jù)X坐標(biāo)進(jìn)行排序。如果 yv > xv,則對(duì)集合a根據(jù)y坐標(biāo)進(jìn)行排序。
- 得到排序后a集合的中位數(shù)m。則以m為斷點(diǎn)，將[0,m-2]索引的點(diǎn)放到a1集合中。將[m,a.count]索引的點(diǎn)放到a2的集合中（m點(diǎn)的索引為m-1）。
- 構(gòu)建節(jié)點(diǎn)，節(jié)點(diǎn)的值為a[m-1],如果操作集合中節(jié)點(diǎn)的個(gè)數(shù)大于1，則左節(jié)點(diǎn)對(duì)[0，m-2]重復(fù)2-5步，右節(jié)點(diǎn)為對(duì)[m,a.count]重復(fù)2-5步；反之，則該節(jié)點(diǎn)為葉子節(jié)點(diǎn)。
3.2 代碼實(shí)現(xiàn)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
private KDTreeNode CreateTreeNode(List<Point> pointList){ if (pointList.Count > 0) { // 計(jì)算方差 double xObtainVariance = ObtainVariance(CreateXList(pointList)); double yObtainVariance = ObtainVariance(CreateYList(pointList)); // 根據(jù)方差確定分裂維度 EnumDivisionType divisionType = SortListByXOrYVariances(xObtainVariance, yObtainVariance, ref pointList); // 獲得中位數(shù) Point medianPoint = ObtainMedian(pointList); int medianIndex = pointList.Count / 2; // 構(gòu)建節(jié)點(diǎn) 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的總體搜索流程先根據(jù)普通的查找找到一個(gè)最近的葉子節(jié)點(diǎn)。但是這個(gè)葉子節(jié)點(diǎn)不一定是最近的點(diǎn)。再進(jìn)行回溯的操作找到最近點(diǎn)。
4.1 KD樹搜索邏輯流程
- 對(duì)于根據(jù)點(diǎn)集構(gòu)建的樹t,以及查找點(diǎn)p.將根節(jié)點(diǎn)作為節(jié)點(diǎn)t進(jìn)行如下的操作
- 如果t為葉子節(jié)點(diǎn)。則得到最近點(diǎn)n的值為t的分裂點(diǎn)的值，跳到第5步;如果t不是葉子節(jié)點(diǎn),進(jìn)行第3步
- 則確定t的分裂方式，如果是按照x軸進(jìn)行分裂，則用p的x值與節(jié)點(diǎn)的分裂點(diǎn)的x值進(jìn)行比較，反之則進(jìn)行Y坐標(biāo)的比較
- 如果p的比較值小于t的比較值，則將t指定為t的左孩子節(jié)點(diǎn)。反之將t指定為t的右孩子節(jié)點(diǎn)，執(zhí)行第2步
- 定義檢索點(diǎn)m，將m設(shè)置為n
- 計(jì)算m與p的距離d1,n與m的距離d2。
- 如果d1 >= d2且有父節(jié)點(diǎn),則將m的父節(jié)點(diǎn)作為m的值執(zhí)行5步，若沒(méi)有父節(jié)點(diǎn)，則得到真正的最近點(diǎn)TN; 如果d1 < d2就表示n點(diǎn)不是最近點(diǎn)，執(zhí)行第8步
- 若n有兄弟節(jié)點(diǎn)，則 n = n的兄弟節(jié)點(diǎn)；若n沒(méi)有兄弟節(jié)點(diǎn)，則 n = n的父節(jié)點(diǎn)。刪除原來(lái)的n節(jié)點(diǎn)。將m的值設(shè)置為新的n節(jié)點(diǎn)；執(zhí)行第6步。
4.2 代碼實(shí)現(xiàn)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
public Point FindNearest(Point searchPoint){ // 按照查找方式尋找最近點(diǎn) Point nearestPoint = DFSSearch(this.rootNode, searchPoint); // 進(jìn)行回溯 return BacktrcakSearch(searchPoint, nearestPoint);}private Point DFSSearch(KDTreeNode node,Point searchPoint,bool pushStack = true){ if(pushStack == true) { // 利用堆棧記錄查詢的路徑，由于樹節(jié)點(diǎn)中沒(méi)有記載父節(jié)點(diǎn)的原因 backtrackStack.Push(node); } if (node.DivisionType == EnumDivisionType.X) { return DFSXsearch(node,searchPoint); } else { return DFSYsearch(node, searchPoint); }}private Point BacktrcakSearch(Point searchPoint,Point nearestPoint){ // 如果記錄路徑的堆棧為空則表示已經(jīng)回溯到根節(jié)點(diǎn)，則查到的最近點(diǎn)就是真正的最近點(diǎn) if (backtrackStack.IsEmpty()) { return nearestPoint; } else { KDTreeNode trackNode = backtrackStack.Pop(); // 分別求回溯點(diǎn)與最近點(diǎn)距查找點(diǎn)的距離 double backtrackDistance = ObtainDistanFromTwoPoint(searchPoint, trackNode.DivisionPoint); double nearestPointDistance = ObtainDistanFromTwoPoint(searchPoint, nearestPoint); if (backtrackDistance < nearestPointDistance) { // 深拷貝節(jié)點(diǎn)的目的是為了避免損壞樹 KDTreeNode searchNode = new KDTreeNode() { DivisionPoint = trackNode.DivisionPoint, DivisionType = trackNode.DivisionType, LeftChild = trackNode.LeftChild, RightChild = trackNode.RightChild }; nearestPoint = DFSBackTrackingSearch(searchNode, searchPoint); } // 遞歸到根節(jié)點(diǎn) return BacktrcakSearch(searchPoint, nearestPoint); }} |
5. 源碼交流
https://github.com/CreamMilk/C-Kd-Tree
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持服務(wù)器之家。
原文鏈接：http://www.cnblogs.com/MaFeng0213/archive/2017/09/26/7598886.html
