什么叫平衡二叉樹(shù)，KD樹(shù)是不是就是平衡二叉樹(shù)呢？

是的。

我們提供的服務(wù)有：成都做網(wǎng)站、網(wǎng)站設(shè)計(jì)、外貿(mào)營(yíng)銷(xiāo)網(wǎng)站建設(shè)、微信公眾號(hào)開(kāi)發(fā)、網(wǎng)站優(yōu)化、網(wǎng)站認(rèn)證、瀾滄ssl等。為成百上千家企事業(yè)單位解決了網(wǎng)站和推廣的問(wèn)題。提供周到的售前咨詢(xún)和貼心的售后服務(wù)，是有科學(xué)管理、有技術(shù)的瀾滄網(wǎng)站制作公司

平衡二叉樹(shù)（Balanced Binary Tree）又被稱(chēng)為AVL樹(shù)（有別于A(yíng)VL算法），且具有以下性質(zhì)：它是一 棵空樹(shù)或它的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1，并且左右兩個(gè)子樹(shù)都是一棵平衡二叉樹(shù)。構(gòu)造與調(diào)整方法 平衡二叉樹(shù)的常用算法有紅黑樹(shù)、AVL、Treap、伸展樹(shù)等。 最小二叉平衡樹(shù)的節(jié)點(diǎn)的公式如下 F(n)=F(n-1)+F(n-2)+1 這個(gè)類(lèi)似于一個(gè)遞歸的數(shù)列，可以參考Fibonacci數(shù)列 1是根節(jié)點(diǎn) F(n-1)是左子樹(shù)的節(jié)點(diǎn)數(shù)量 F(n-2)是右子數(shù)的節(jié)點(diǎn)數(shù)量。

kd-

樹(shù)（

k

維搜索樹(shù)）是把二叉搜索樹(shù)推廣到多維數(shù)據(jù)的一種主存數(shù)據(jù)結(jié)構(gòu)。我們將先

介紹這種思想，然后討論怎樣使這種思想適合存儲(chǔ)的塊模型。

kd-

樹(shù)是一個(gè)二叉樹(shù)，它的內(nèi)

部結(jié)點(diǎn)有一個(gè)相關(guān)聯(lián)的屬性

a

和一個(gè)值

V

，它將數(shù)據(jù)點(diǎn)集分成兩個(gè)部分：

a

值小于

V

的部分

和

a

值大于等于

V

的部分。

由于所有維的屬性在層間交替出現(xiàn)，

所以樹(shù)的不同層上的屬性是

不同的

KNN算法-4-算法優(yōu)化-KD樹(shù)

KNN算法的重要步驟是對(duì)所有的實(shí)例點(diǎn)進(jìn)行快速k近鄰搜索。如果采用線(xiàn)性?huà)呙瑁╨inear scan），要計(jì)算輸入點(diǎn)與每一個(gè)點(diǎn)的距離，時(shí)間復(fù)雜度非常高。因此在查詢(xún)操作時(shí)，可以使用kd樹(shù)對(duì)查詢(xún)操作進(jìn)行優(yōu)化。

Kd-樹(shù)是K-dimension tree的縮寫(xiě)，是對(duì)數(shù)據(jù)點(diǎn)在k維空間（如二維(x，y)，三維(x，y，z)，k維(x1，y，z..)）中劃分的一種數(shù)據(jù)結(jié)構(gòu)，主要應(yīng)用于多維空間關(guān)鍵數(shù)據(jù)的搜索（如：范圍搜索和最近鄰搜索）。本質(zhì)上說(shuō)，Kd-樹(shù)就是一種平衡二叉樹(shù)。

k-d tree是每個(gè)節(jié)點(diǎn)均為k維樣本點(diǎn)的二叉樹(shù)，其上的每個(gè)樣本點(diǎn)代表一個(gè)超平面，該超平面垂直于當(dāng)前劃分維度的坐標(biāo)軸，并在該維度上將空間劃分為兩部分，一部分在其左子樹(shù)，另一部分在其右子樹(shù)。即若當(dāng)前節(jié)點(diǎn)的劃分維度為d，其左子樹(shù)上所有點(diǎn)在d維的坐標(biāo)值均小于當(dāng)前值，右子樹(shù)上所有點(diǎn)在d維的坐標(biāo)值均大于等于當(dāng)前值，本定義對(duì)其任意子節(jié)點(diǎn)均成立。

必須搞清楚的是，k-d樹(shù)是一種空間劃分樹(shù)，說(shuō)白了，就是把整個(gè)空間劃分為特定的幾個(gè)部分，然后在特定空間的部分內(nèi)進(jìn)行相關(guān)搜索操作。想像一個(gè)三維(多維有點(diǎn)為難你的想象力了)空間，kd樹(shù)按照一定的劃分規(guī)則把這個(gè)三維空間劃分了多個(gè)空間，如下圖所示：

首先，邊框?yàn)榧t色的豎直平面將整個(gè)空間劃分為兩部分，此兩部分又分別被邊框?yàn)榫G色的水平平面劃分為上下兩部分。最后此4個(gè)子空間又分別被邊框?yàn)樗{(lán)色的豎直平面分割為兩部分，變?yōu)?個(gè)子空間，此8個(gè)子空間即為葉子節(jié)點(diǎn)。

常規(guī)的k-d tree的構(gòu)建過(guò)程為：

對(duì)于構(gòu)建過(guò)程，有兩個(gè)優(yōu)化點(diǎn)：

例子：采用常規(guī)的構(gòu)建方式，以二維平面點(diǎn)(x,y)的集合(2,3)，(5,4)，(9,6)，(4,7)，(8,1)，(7,2) 為例結(jié)合下圖來(lái)說(shuō)明k-d tree的構(gòu)建過(guò)程：

如上算法所述，kd樹(shù)的構(gòu)建是一個(gè)遞歸過(guò)程，我們對(duì)左子空間和右子空間內(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ù)中，kd代表k-dimension，每個(gè)節(jié)點(diǎn)即為一個(gè)k維的點(diǎn)。每個(gè)非葉節(jié)點(diǎn)可以想象為一個(gè)分割超平面，用垂直于坐標(biāo)軸的超平面將空間分為兩個(gè)部分，這樣遞歸的從根節(jié)點(diǎn)不停的劃分，直到?jīng)]有實(shí)例為止。經(jīng)典的構(gòu)造k-d tree的規(guī)則如下：

kd樹(shù)的檢索是KNN算法至關(guān)重要的一步，給定點(diǎn)p，查詢(xún)數(shù)據(jù)集中與其距離最近點(diǎn)的過(guò)程即為最近鄰搜索。

如在構(gòu)建好的k-d tree上搜索(3,5)的最近鄰時(shí)，對(duì)二維空間的最近鄰搜索過(guò)程作分析。

首先從根節(jié)點(diǎn)(7,2)出發(fā)，將當(dāng)前最近鄰設(shè)為(7,2)，對(duì)該k-d tree作深度優(yōu)先遍歷。

以(3,5)為圓心，其到(7,2)的距離為半徑畫(huà)圓（多維空間為超球面），可以看出(8,1)右側(cè)的區(qū)域與該圓不相交，所以(8,1)的右子樹(shù)全部忽略。

接著走到(7,2)左子樹(shù)根節(jié)點(diǎn)(5,4)，與原最近鄰對(duì)比距離后，更新當(dāng)前最近鄰為(5,4)。

以(3,5)為圓心，其到(5,4)的距離為半徑畫(huà)圓，發(fā)現(xiàn)(7,2)右側(cè)的區(qū)域與該圓不相交，忽略該側(cè)所有節(jié)點(diǎn)，這樣(7,2)的整個(gè)右子樹(shù)被標(biāo)記為已忽略。

遍歷完(5,4)的左右葉子節(jié)點(diǎn)，發(fā)現(xiàn)與當(dāng)前最優(yōu)距離相等，不更新最近鄰。所以(3,5)的最近鄰為(5,4)。

舉例：查詢(xún)點(diǎn)（2.1,3.1）

星號(hào)表示要查詢(xún)的點(diǎn)（2.1,3.1）。通過(guò)二叉搜索，順著搜索路徑很快就能找到最鄰近的近似點(diǎn)，也就是葉子節(jié)點(diǎn)（2,3）。而找到的葉子節(jié)點(diǎn)并不一定就是最鄰近的，最鄰近肯定距離查詢(xún)點(diǎn)更近，應(yīng)該位于以查詢(xún)點(diǎn)為圓心且通過(guò)葉子節(jié)點(diǎn)的圓域內(nèi)。為了找到真正的最近鄰，還需要進(jìn)行相關(guān)的‘回溯'操作。也就是說(shuō)，算法首先沿搜索路徑反向查找是否有距離查詢(xún)點(diǎn)更近的數(shù)據(jù)點(diǎn)。

舉例：查詢(xún)點(diǎn)（2，4.5）

一個(gè)復(fù)雜點(diǎn)了例子如查找點(diǎn)為（2，4.5），具體步驟依次如下：

上述兩次實(shí)例表明，當(dāng)查詢(xún)點(diǎn)的鄰域與分割超平面兩側(cè)空間交割時(shí)，需要查找另一側(cè)子空間，導(dǎo)致檢索過(guò)程復(fù)雜，效率下降。

一般來(lái)講，最臨近搜索只需要檢測(cè)幾個(gè)葉子結(jié)點(diǎn)即可，如下圖所示：　

但是，如果當(dāng)實(shí)例點(diǎn)的分布比較糟糕時(shí)，幾乎要遍歷所有的結(jié)點(diǎn)，如下所示：

研究表明N個(gè)節(jié)點(diǎn)的K維k-d樹(shù)搜索過(guò)程時(shí)間復(fù)雜度為： 。

同時(shí)，以上為了介紹方便，討論的是二維或三維情形。但在實(shí)際的應(yīng)用中，如SIFT特征矢量128維，SURF特征矢量64維，維度都比較大，直接利用k-d樹(shù)快速檢索（維數(shù)不超過(guò)20）的性能急劇下降，幾乎接近貪婪線(xiàn)性?huà)呙?。假設(shè)數(shù)據(jù)集的維數(shù)為D，一般來(lái)說(shuō)要求數(shù)據(jù)的規(guī)模N滿(mǎn)足N?2D，才能達(dá)到高效的搜索。

Sklearn中有KDTree的實(shí)現(xiàn)，僅構(gòu)建了一個(gè)二維空間的k-d tree，然后對(duì)其作k近鄰搜索及指定半徑的范圍搜索。多維空間的檢索，調(diào)用方式與此例相差無(wú)多。

2 Kd樹(shù)的構(gòu)造與搜索

實(shí)現(xiàn)kNN算法時(shí)，最簡(jiǎn)單的實(shí)現(xiàn)方法就是線(xiàn)性?huà)呙?，正如我們上一章?jié)內(nèi)容介紹的一樣- K近鄰算法 ，需要計(jì)算輸入實(shí)例與每一個(gè)訓(xùn)練樣本的距離。當(dāng)訓(xùn)練集很大時(shí)，會(huì)非常耗時(shí)。

為了提高kNN搜索的效率，可以考慮使用特殊的結(jié)構(gòu)存儲(chǔ)訓(xùn)練數(shù)據(jù)，以減少計(jì)算距離的次數(shù)，KD-Tree就是其中的一種方法。

K維空間數(shù)據(jù)集

其中

隨機(jī)生成 13 個(gè)點(diǎn)作為我們的數(shù)據(jù)集

首先先沿 x 坐標(biāo)進(jìn)行切分，我們選出 x 坐標(biāo)的中位點(diǎn)，獲取最根部節(jié)點(diǎn)的坐標(biāo)

并且按照該點(diǎn)的x坐標(biāo)將空間進(jìn)行切分，所有 x 坐標(biāo)小于 6.27 的數(shù)據(jù)用于構(gòu)建左分支，x坐標(biāo)大于 6.27 的點(diǎn)用于構(gòu)建右分支。

在下一步中 ,對(duì)應(yīng) y 軸，左右兩邊再按照 y 軸的排序進(jìn)行切分，中位點(diǎn)記載于左右枝的節(jié)點(diǎn)。得到下面的樹(shù)，左邊的 x 是指這該層的節(jié)點(diǎn)都是沿 x 軸進(jìn)行分割的。

空間的切分如下

下一步中 ，對(duì)應(yīng) x 軸，所以下面再按照 x 坐標(biāo)進(jìn)行排序和切分，有

最后只剩下了葉子結(jié)點(diǎn)，就此完成了 kd 樹(shù)的構(gòu)造。

輸入：已構(gòu)造的kd樹(shù)，目標(biāo)點(diǎn)x

輸出：x的k個(gè)最近鄰集合L

KD-Tree的平均時(shí)間復(fù)雜度為 ，N為訓(xùn)練樣本的數(shù)量。

KD-Tree試用于訓(xùn)練樣本數(shù)遠(yuǎn)大于空間維度的k近鄰搜索。當(dāng)空間維數(shù)接近訓(xùn)練樣本數(shù)時(shí)，他的效率會(huì)迅速下降，幾乎接近線(xiàn)性?huà)呙琛?/p>

設(shè)我們想查詢(xún)的點(diǎn)為 p=(?1,?5)，設(shè)距離函數(shù)是普通的距離，我們想找距離目標(biāo)點(diǎn)最近的 k=3 個(gè)點(diǎn)。如下：

首先我們按照構(gòu)造好的KD-Tree，從根結(jié)點(diǎn)開(kāi)始查找

和這個(gè)節(jié)點(diǎn)的 x 軸比較一下，p 的 x 軸更小。因此我們向左枝進(jìn)行搜索：

接下來(lái)需要對(duì)比 y 軸

p 的 y 值更小，因此向左枝進(jìn)行搜索：

這個(gè)節(jié)點(diǎn)只有一個(gè)子枝，就不需要對(duì)比了。由此找到了葉子節(jié)點(diǎn) (?4.6,?10.55)。

在二維圖上是藍(lán)色的點(diǎn)

此時(shí)我們要執(zhí)行第二步，將當(dāng)前結(jié)點(diǎn)插入到集合L中，并記錄下 L=[(?4.6,?10.55)]。訪(fǎng)問(wèn)過(guò)的節(jié)點(diǎn)就在二叉樹(shù)上顯示為被劃掉的好了。

然后執(zhí)行第三步，不是最頂端節(jié)點(diǎn)。我回退。上面的結(jié)點(diǎn)是 (?6.88,?5.4)。

執(zhí)行 3a，因?yàn)槲覀冇涗浵碌狞c(diǎn)只有一個(gè)，小于 k=3，所以也將當(dāng)前節(jié)點(diǎn)記錄下，插入到集合L中，有 L=[(?4.6,?10.55),(?6.88,?5.4)].。 因?yàn)楫?dāng)前節(jié)點(diǎn)的左枝是空的，所以直接跳過(guò)，繼續(xù)回退，判斷不是頂部根節(jié)點(diǎn)

由于還是不夠三個(gè)點(diǎn)，于是將當(dāng)前點(diǎn)也插入到集合L中，有 L=[(?4.6,?10.55),(?6.88,?5.4),(1.24,?2.86)]。

此時(shí)發(fā)現(xiàn)，當(dāng)前節(jié)點(diǎn)有其他的分枝，執(zhí)行3b，計(jì)算得出 p 點(diǎn)和 L 中的三個(gè)點(diǎn)的距離分別是 6.62, 5.89, 3.10，但是 p 和當(dāng)前節(jié)點(diǎn)的分割線(xiàn)的距離只有 2.14，小于與 L 的最大距離：

因此，在分割線(xiàn)的另一端可能有更近的點(diǎn)。于是我們?cè)诋?dāng)前結(jié)點(diǎn)的另一個(gè)分枝從頭執(zhí)行步驟1。好，我們?cè)诩t線(xiàn)這里：

此時(shí)處于x軸切分，因此要用 p 和這個(gè)節(jié)點(diǎn)比較 x 坐標(biāo):

p 的 x 坐標(biāo)更大，因此探索右枝 (1.75,12.26)，并且發(fā)現(xiàn)右枝已經(jīng)是最底部節(jié)點(diǎn)，執(zhí)行步驟2與3a。

經(jīng)計(jì)算，(1.75,12.26) 與 p 的距離是 17.48，要大于 p 與 L 的距離，因此我們不將其放入記錄中。

然后 回退，判斷出不是頂端節(jié)點(diǎn)，往上爬。

執(zhí)行3a，這個(gè)節(jié)點(diǎn)與 p 的距離是 4.91，要小于 p 與 L 的最大距離 6.62。

因此，我們用這個(gè)新的節(jié)點(diǎn)替代 L 中離 p 最遠(yuǎn)的 (?4.6,?10.55)。

然后3b，我們比對(duì) p 和當(dāng)前節(jié)點(diǎn)的分割線(xiàn)的距離

這個(gè)距離小于 L 與 p 的最大距離，因此我們要到當(dāng)前節(jié)點(diǎn)的另一個(gè)枝執(zhí)行步驟1。當(dāng)然，那個(gè)枝只有一個(gè)點(diǎn)。

計(jì)算距離發(fā)現(xiàn)這個(gè)點(diǎn)離 p 比 L 更遠(yuǎn)，因此不進(jìn)行替代。

然后回退，不是根結(jié)點(diǎn)，我們向上爬

這個(gè)是已經(jīng)訪(fǎng)問(wèn)過(guò)的了，所以再向上爬

再爬

此時(shí)到頂點(diǎn)了 。所以完了嗎？當(dāng)然不，還要執(zhí)行3b呢。現(xiàn)在是步驟1的回合。

我們進(jìn)行計(jì)算比對(duì)發(fā)現(xiàn)頂端節(jié)點(diǎn)與p的距離比L還要更遠(yuǎn)，因此不進(jìn)行更新。

然后計(jì)算 p 和分割線(xiàn)的距離發(fā)現(xiàn)也是更遠(yuǎn)。

因此也不需要檢查另一個(gè)分枝。

判斷當(dāng)前節(jié)點(diǎn)是頂點(diǎn)，因此計(jì)算完成！輸出距離 p 最近的三個(gè)樣本是 L=[(?6.88,?5.4),(1.24,?2.86),(?2.96,?2.5)]。

聲明：此文章為本人學(xué)習(xí)筆記，參考于：