數(shù)據(jù)結(jié)構(gòu)之KD樹(shù)

1、KD 樹(shù)算法KD樹(shù)的應(yīng)用背景什么是KD樹(shù)KD樹(shù)的基本操作a) KD樹(shù)的構(gòu)建b) KD樹(shù)的插入c)KD樹(shù)的刪除d) KD樹(shù)的最近鄰搜索算法總結(jié)KD 樹(shù) SIFT算法中做特征點(diǎn)匹配的時(shí)候就會(huì)利用到k-d樹(shù)。而特征點(diǎn)匹配實(shí)際上就是一個(gè)通過(guò)距離函數(shù)在高維矢量之間進(jìn)行相似性檢索的問(wèn)題。針對(duì)如何快速而準(zhǔn)確地找到查詢(xún)點(diǎn)的近鄰，現(xiàn)在提出了很多高維空間索引結(jié)構(gòu)和近似查詢(xún)的算法，k-d樹(shù)就是其中一種。背景KD樹(shù)的應(yīng)用背景什么是KD樹(shù)KD樹(shù)的基本操作a) KD樹(shù)的構(gòu)建b) KD樹(shù)的插入c)KD樹(shù)的刪除d) KD樹(shù)的最近鄰搜索算法總結(jié)KD 樹(shù) Kd-樹(shù)是對(duì)數(shù)據(jù)點(diǎn)在k維空間（如二維(x，y)，三維(x，y，z)，k維(

2、x1，y，z.)）中劃分的一種數(shù)據(jù)結(jié)構(gòu)，主要應(yīng)用于多維空間關(guān)鍵數(shù)據(jù)的搜索（如：范圍搜索和最近鄰搜索）。本質(zhì)上說(shuō)，Kd-樹(shù)就是一種平衡二叉樹(shù)。KD樹(shù)的定義 比如kd樹(shù)按照一定的劃分規(guī)則把這個(gè)三維空間劃分了多個(gè)空間，如下圖所示：KD樹(shù)的定義KD樹(shù)的應(yīng)用背景什么是KD樹(shù)KD樹(shù)的基本操作a) KD樹(shù)的構(gòu)建b) KD樹(shù)的插入c)KD樹(shù)的刪除d) KD樹(shù)的最近鄰搜索算法總結(jié)KD 樹(shù) KD樹(shù)構(gòu)建的偽代碼如下圖所示：KD樹(shù)的構(gòu)建 假設(shè)有6個(gè)二維數(shù)據(jù)點(diǎn)(2,3)，(5,4)，(9,6)，(4,7)，(8,1)，(7,2)，數(shù)據(jù)點(diǎn)位于二維空間內(nèi)，如下圖所示。KD樹(shù)的構(gòu)建 確定：split域=x。具體是：6個(gè)數(shù)據(jù)點(diǎn)

3、在x，y維度上的數(shù)據(jù)方差分別為39，28.63，所以在x軸上方差更大，故split域值為x； 確定：Node-data = （7,2）。具體是：根據(jù)x維上的值將數(shù)據(jù)排序，6個(gè)數(shù)據(jù)的中值(所謂中值，即中間大小的值)為7，所以Node-data域位數(shù)據(jù)點(diǎn)（7,2）。這樣，該節(jié)點(diǎn)的分割超平面就是通過(guò)（7,2）并垂直于：split=x軸的直線(xiàn)x=7； 確定：左子空間和右子空間。具體是：分割超平面x=7將整個(gè)空間分為兩部分：x=7的部分為左子空間，包含3個(gè)節(jié)點(diǎn)=(2,3),(5,4),(4,7)；另一部分為右子空間，包含2個(gè)節(jié)點(diǎn)=(9,6)，(8,1)； 如上算法所述，kd樹(shù)的構(gòu)建是一個(gè)遞歸過(guò)程，我們對(duì)

4、左子空間和右子空間內(nèi)的數(shù)據(jù)重復(fù)根節(jié)點(diǎn)的過(guò)程就可以得到一級(jí)子節(jié)點(diǎn)（5,4）和（9,6），同時(shí)將空間和數(shù)據(jù)集進(jìn)一步細(xì)分，如此往復(fù)直到空間中只包含一個(gè)數(shù)據(jù)點(diǎn)。KD樹(shù)的構(gòu)建KD樹(shù)的構(gòu)建KD樹(shù)的應(yīng)用背景什么是KD樹(shù)KD樹(shù)的基本操作a) KD樹(shù)的構(gòu)建b) KD樹(shù)的插入c)KD樹(shù)的刪除d) KD樹(shù)的最近鄰搜索算法總結(jié)KD 樹(shù) 元素插入到一個(gè)K-D樹(shù)的方法和二叉檢索樹(shù)類(lèi)似。本質(zhì)上，在偶數(shù)層比較x坐標(biāo)值，而在奇數(shù)層比較y坐標(biāo)值。當(dāng)我們到達(dá)了樹(shù)的底部，（也就是當(dāng)一個(gè)空指針出 現(xiàn)），我們也就找到了結(jié)點(diǎn)將要插入的位置。生成的K-D樹(shù)的形狀依賴(lài)于結(jié)點(diǎn)插入時(shí)的順序。給定N個(gè)點(diǎn)，其中一個(gè)結(jié)點(diǎn)插入和檢索的平均代價(jià)是 O(lo

5、g2N)。KD樹(shù)的插入 插入順序?yàn)?a) Chicago, (b) Mobile, (c) Toronto, and (d) Buffalo，建立空間K-D樹(shù)的示例：KD樹(shù)的插入KD樹(shù)的插入KD樹(shù)的應(yīng)用背景什么是KD樹(shù)KD樹(shù)的基本操作a) KD樹(shù)的構(gòu)建b) KD樹(shù)的插入c)KD樹(shù)的刪除d) KD樹(shù)的最近鄰搜索算法總結(jié)KD 樹(shù) KD樹(shù)的刪除可以用遞歸程序來(lái)實(shí)現(xiàn)。我們假設(shè)希望從K-D樹(shù)中刪除結(jié)點(diǎn)（a,b）。如果（a,b）的兩個(gè)子樹(shù)都為空，則用空樹(shù)來(lái)代替（a,b）。否則，在 （a,b）的子樹(shù)中尋找一個(gè)合適的結(jié)點(diǎn)來(lái)代替它，譬如(c,d)，則遞歸地從K-D樹(shù)中刪除（c,d）。一旦(c,d)已經(jīng)被刪除，則

6、用（c,d）代替 （a,b）。假設(shè)(a,b)是一個(gè)X識(shí)別器，那么，它得替代節(jié)點(diǎn)要么是（a,b）左子樹(shù)中的X坐標(biāo)最大值的結(jié)點(diǎn)，要么是（a,b）右子樹(shù)中x坐標(biāo)最小值的結(jié)點(diǎn)。KD樹(shù)的刪除 如下圖所示，原始圖像及對(duì)應(yīng)的kd樹(shù)，現(xiàn)在要?jiǎng)h除圖中的A結(jié)點(diǎn)KD樹(shù)的刪除 要?jiǎng)h除上圖中結(jié)點(diǎn)A，選擇結(jié)點(diǎn)A的右子樹(shù)中X坐標(biāo)值最小的結(jié)點(diǎn)，這里是C，C成為根，如下圖：KD樹(shù)的刪除 從C的右子樹(shù)中找出一個(gè)結(jié)點(diǎn)代替先前C的位置，如下圖所示：KD樹(shù)的刪除 這里是D，并將D的左子樹(shù)轉(zhuǎn)為它的右子樹(shù)，D代替先前C的位置，如下圖：KD樹(shù)的刪除 在D的新右子樹(shù)中，找X坐標(biāo)最小的結(jié)點(diǎn)，這里為H，H代替D的位置，KD樹(shù)的刪除 在D的右子樹(shù)中

7、找到一個(gè)Y坐標(biāo)最小的值，這里是I，將I代替原先H的位置，從而A結(jié)點(diǎn)從圖中順利刪除，如下圖所示：KD樹(shù)的刪除KD樹(shù)的應(yīng)用背景什么是KD樹(shù)KD樹(shù)的基本操作a) KD樹(shù)的構(gòu)建b) KD樹(shù)的插入c)KD樹(shù)的刪除d) KD樹(shù)的最近鄰搜索算法總結(jié)KD 樹(shù) k-d樹(shù)查詢(xún)算法的偽代碼如下所示：KD樹(shù)的最近鄰搜索算法 查詢(xún)點(diǎn)（查詢(xún)點(diǎn)（2 2，4.54.5），步驟如下：，步驟如下： 同樣先進(jìn)行二叉查找，先從 （7,2）查找到（5,4）節(jié)點(diǎn)，在進(jìn)行查找時(shí)是由y = 4為分割超平面的，由于查找點(diǎn)為y值為4.5，因此進(jìn)入右子空間查找到（4,7），形成搜索路徑，但 （4,7）與目標(biāo)查找點(diǎn)的距離為3.202，而（5,4）與

8、查找點(diǎn)之間的距離為3.041，所以（5,4）為查詢(xún)點(diǎn)的最近點(diǎn)；KD樹(shù)的最近鄰搜索算法 以（2，4.5）為圓心，以3.041為半徑作圓，如下圖所示?？梢?jiàn)該圓和y = 4超平面交割，所以需要進(jìn)入（5,4）左子空間進(jìn)行查找，也就是將（2,3）節(jié)點(diǎn)加入搜索路徑中得；于是接著搜索至（2,3）葉子節(jié)點(diǎn)，（2,3）距離（2,4.5）比（5,4）要近，所以最近鄰點(diǎn)更新為（2，3），最近距離更新為1.5；KD樹(shù)的最近鄰搜索算法 回溯查找至（5,4），直到最后回溯到根結(jié)點(diǎn)（7,2）的時(shí)候，以（2,4.5）為圓心1.5為半徑作圓，并不和x = 7分割超平面交割，如下圖所示。至此，搜索路徑回溯完，返回最近鄰點(diǎn)（2,3），最近距離1.5。KD樹(shù)的最近鄰搜索算法KD樹(shù)的最近鄰搜索算法KD樹(shù)的應(yīng)用背景什么是KD樹(shù)KD樹(shù)的基本操作a) KD樹(shù)的構(gòu)建b) KD