從B樹刪除

我在我的家庭作業中有關於最小分支因子t = 2的B樹刪除的問題。從B樹刪除

    [P] 
      / \ 
      /  \ 
      /  \ 
      /   \ 
     /   \  
     [G][L]   [W] 
    /| \  / \ 
    / | \  / \ 
    / |  \ /  \ 
    BD  J  N  R  Y 
/| \ /\ /\ /\ /\ 
A C F I K M O Q ST X Z

現在從上面的樹除去Y後，我得到了最終的樹..

    [P] 
      / \ 
      /  \ 
      /  \ 
      /   \ 
     /   \  
     [G][L]   [W] 
    /| \  / \ 
    / | \  / \ 
    / |  \ /  \ 
    BD  J  N  R  X 
/| \ /\ /\ /\ /\ 
A C F I K M O Q S T Z

這會不會是最後的樹Ÿ刪除後......我不知道這就是爲什麼在這裏張貼到是corrected..thankss

來源

2013-10-19 Daket

T怎麼能在W的右子樹上？ – Justin

我不認爲這是正確的，T不能在W的因爲T談到W.

前

    [P] 
      / \ 
      /  \ 
      /  \ 
      /   \ 
     /   \  
     [G][L]   [T] 
    /| \  / \ 
    / | \  / \ 
    / |  \ /  \ 
    BD  J  N  R  X 
/| \ /\ /\ /\ /\ 
A C F I K M O Q S W Z

右子樹

步驟如下：

刪除Y：

    [P] 
      / \ 
      /  \ 
      /  \ 
      /   \ 
     /   \  
     [G][L]   [W] 
    /| \  / \ 
    / | \  / \ 
    / |  \ /  \ 
    BD  J  N  R  null 
/| \ /\ /\ /\ /\ 
A C F I K M O Q ST X Z

替換右子樹（Z）最小的，平衡的個Z舊的位置

    [P] 
      / \ 
      /  \ 
      /  \ 
      /   \ 
     /   \  
     [G][L]   [W] 
    /| \  / \ 
    / | \  / \ 
    / |  \ /  \ 
    BD  J  N  R  Z 
/| \ /\ /\ /\ /
A C F I K M O Q ST X

無法從兄弟姐妹借錢（ X）合併Z的子女：

    [P] 
      / \ 
      /  \ 
      /  \ 
      /   \ 
     /   \  
     [G][L]   [W] 
    /| \  / \ 
    / | \  / \ 
    / |  \ /  \ 
    BD  J  N  R  [X,Z] 
/| \ /\ /\ /\ 
A C F I K M O Q ST

不能從兄弟姐妹（R）借用，合併子女仁爲W：

    [P] 
      / \ 
      /  \ 
      /  \ 
      /   \ 
     /   \  
     [G][L]  [Q,R,S,T,W,X,Z] 
    /| \  
    / | \  
    / |  \ 
    BD  J  N 
/| \ /\ /\ 
A C F I K M O

合併節點（先前W）現過大，平分：

    [P] 
      / \ 
      /  \ 
      /  \ 
      /   \ 
     /   \  
     [G][L]   [T] 
    /| \  / \ 
    / | \  [Q,R,S] [W,X,Z] 
    / |  \ 
    BD  J  N 
/| \ /\ /\ 
A C F I K M O

的T左節點現在是過大，平分：

    [P] 
      / \ 
      /  \ 
      /  \ 
      /   \ 
     /   \  
     [G][L]   [T] 
    /| \  / \ 
    / | \  /[W,X,Z] 
    / |  \ /
    BD  J  N  R 
/| \ /\ /\ /\ 
A C F I K M O Q S

T的右節點也太大，均勻分割：

    [P] 
      / \ 
      /  \ 
      /  \ 
      /   \ 
     /   \  
     [G][L]   [T] 
    /| \  / \ 
    / | \  / \ 
    / |  \ /  \ 
    BD  J  N  R  X 
/| \ /\ /\ /\ /\ 
A C F I K M O Q S W Z

來源

2013-10-19 16:54:52 Justin

你在這裏應用的刪除案例：我沒有得到這個答案...我現在知道，T不能在右邊的子樹W ... – Daket

@ambani我已經更新了我的答案，以幫助解釋。 – Justin

謝謝，我明白了......感謝一噸...... :) – Daket

這是個好問題。 L去根， P去它的右邊的孩子，坐在W N附近，它的孩子成爲刪除Y的P 的左邊孩子，W必須去掉R和Y的中間部分 Y在X和Z之間下降現在你可以刪除Y ...

  [ L ] 
      / \

!!!!!!/\ /\ /\ /\
[G] [P] /\/\ /\/\ /\/\ [B d] [J] N r個W¯¯
/| \/\/\// | \
A C F I K M O Q ST X Z ---> Y

來源

2013-10-24 18:24:32 strftm

  [ L ] 
      / \ 
     /  \ 
     /  \ 
     /   \ 
     /   \  
     [G]    [P] 
    /\   / \ 
    / \  / \ 
    / \  /  \ 
[B D]  [J]  N  R W  
/| \ /\ /\ /| \  
A C F I K M O Q ST X Z --->Y

來源

2013-10-24 18:27:46 strftm

回答

相關問題