在刪除根節點後重新平衡2-3樹的正確方法

首先我除去22，並通過其在順序後繼28.

其次我平衡所得到的樹替換它，由空節點移動到左邊。結果樹在下面。

正在向正確的過程移動28，並且我是否正確地平衡了左側？

  22,34 
    / | \ 
    16  28 37 
/\ /\ /\ 
15 21 25 33 35 43 

     [28],34 
    / | \ 
    16  *  37 
/\ /\ /\ 
15 21 25 33 35 43 

      34 
     /  \ 
     16,28  37 
    / | \ /\ 
    15 21,25 33 35 43

謝謝！

來源

2016-02-28 eman_44

2-3樹的平衡是所有的子樹都是相同的高度。在我看來，情況就是這樣。 – selalerer

22的有序接班人是25. –

是的，這是一個錯誤。所以現在我只需要在中間節點中合併（28,33），但是它們不再處於同一高度。重新平衡的左右子樹將如何顯示？ –

從

 22,34 
/ |  \ 
    16  28  37 
/\ /\ /\ 
15 21 25 33 35 43 ,

刪除22我們通過其有序繼任25替換它，留一孔（*）。

 25,34 
/ |  \ 
    16  28  37 
/\ /\ /\ 
15 21 * 33 35 43

我們不能通過借用來修復這個洞，所以我們把它的父母合併到它的兄弟姐妹中，讓它向上移動。

 25,34 
/ |  \ 
    16  *  37 
/\  | /\ 
15 21 28,33 35 43

孔現在有兩個兄弟姐妹，所以我們可以重新分配父的關鍵之一了。

  34 
    /  \ 
    16,25  37 
/| \ /\ 
15 21 28,33 35 43

（我是從this set of lecture notes工作。不要打擾這裏識記詳細信息，除非它是一個考試。即使這樣......我真的希望數據結構課程並不強調平衡搜索樹的程度他們這樣做。）

來源

2016-02-28 19:10:21

必須贊同搜索樹註釋的重點，但這確實是我學習如何調試代碼和遞歸，兩個非常重要的技巧 –

非常感謝解釋！ –

在刪除根節點後重新平衡2-3樹的正確方法

回答

相關問題