在删除根节点后重新平衡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树的正确方法

回答

相关问题