熱線電話：13121318867

登錄
首頁精彩閱讀KD樹的刪除?_數據分析師
KD樹的刪除?_數據分析師
2014-12-03
收藏

KD樹的刪除_數據分析師

 KD樹的刪除可以用遞歸程序來實現。我們假設希望從K-D樹中刪除結點（a,b）。如果（a,b）的兩個子樹都為空，則用空樹來代替（a,b）。否則，在（a,b）的子樹中尋找一個合適的結點來代替它，譬如(c,d)，則遞歸地從K-D樹中刪除（c,d）。一旦(c,d)已經被刪除，則用（c,d）代替（a,b）。假設(a,b)是一個X識別器，那么，它得替代節點要么是（a,b）左子樹中的X坐標最大值的結點，要么是（a,b）右子樹中x坐標最小值的結點。
    也就是說，跟普通二叉樹(包括如下圖所示的紅黑樹)結點的刪除是同樣的思想：用被刪除節點A的左子樹的最右節點或者A的右子樹的最左節點作為替代A的節點(比如，下圖紅黑樹中，若要刪除根結點26，第一步便是用23或28取代根結點26)。
   當(a,b)的右子樹為空時，找到（a,b）左子樹中具有x坐標最大的結點，譬如（c,d），將(a,b)的左子樹放到(c,d)的右子樹中，且在樹中從它的上一層遞歸地應用刪除過程（也就是（a,b）的左子樹） 。
    下面來舉一個實際的例子(來源：中國地質大學電子課件，原課件錯誤已經在下文中訂正)，如下圖所示，原始圖像及對應的kd樹，現在要刪除圖中的A結點，請看一系列刪除步驟：
    要刪除上圖中結點A，選擇結點A的右子樹中X坐標值最小的結點，這里是C，C成為根，如下圖：
     從C的右子樹中找出一個結點代替先前C的位置，
    這里是D，并將D的左子樹轉為它的右子樹，D代替先前C的位置，如下圖：
    在D的新右子樹中，找X坐標最小的結點，這里為H，H代替D的位置，
    在D的右子樹中找到一個Y坐標最小的值，這里是I，將I代替原先H的位置，從而A結點從圖中順利刪除，如下圖所示：
    從一個K-D樹中刪除結點(a,b)的問題變成了在(a,b)的子樹中尋找x坐標為最小的結點。不幸的是尋找最小x坐標值的結點比二叉檢索樹中解決類似的問題要復雜得多。特別是雖然最小x坐標值的結點一定在x識別器的左子樹中，但它同樣可在y識別器的兩個子樹中。因此關系到檢索，且必須注意檢索坐標，以使在每個奇數層僅檢索2個子樹中的一個。
    從K-D樹中刪除一個結點是代價很高的，很清楚刪除子樹的根受到子樹中結點個數的限制。用TPL（T）表示樹T總的路徑長度?？煽闯鰳渲凶訕浯笮〉目偤蜑門PL（T）+N。 以隨機方式插入N個點形成樹的TPL是O(N*log2N),這就意味著從一個隨機形成的K-D樹中刪除一個隨機選取的結點平均代價的上界是O(log2N) 。CDA數據分析師官網


CDA數據分析師考試相關入口一覽（建議收藏）：

? 想報名CDA認證考試，點擊>>>   “CDA報名” 了解CDA考試詳情；

? 想學習CDA考試教材，點擊>>> “CDA教材” 了解CDA考試詳情；

? 想加入CDA考試題庫，點擊>>> “CDA題庫” 了解CDA考試詳情；

? 想了解CDA考試含金量，點擊>>> “CDA含金量” 了解CDA考試詳情；

數據分析

數據分析咨詢請掃描二維碼

若不方便掃碼，搜微信號：CDAshujufenxi

上一篇隨機森林 vs XGBoost vs 決策樹：算法選擇中的
下一篇圖論在大數據分析中的作用！
數據分析師考試動態
CDA報考指南
數據分析學習
數據分析師資訊
更多

CDA教育閉環

常見問題

關于我們

CDA數據分析師公眾號

  • CDA數據分析師公眾號

CDA考試中心小程序

  • CDA考試中心服務號

CDA數據分析師App下載

  • CDA數據分析師App下載
Copyright © 2015-2021, www.ruiqisteel.com All Rights Reserved. CDA數據分析師(北京國富如荷網絡科技有限公司) 版權所有 京ICP備11001960號-9 京公網安備 11010802034615號 經營許可證編號：京B2-20210330
聯系電話：13321103290 (微信同號)

OK
客服在線
立即咨詢
日韩人妻系列无码专区视频,先锋高清无码,无码免费视欧非,国精产品一区一区三区无码
客服在線
立即咨詢