删除根节点后重新平衡 2-3 树的正确方法

Question

目标是从根节点中删除 22 并重新平衡树。

首先，我删除 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 

谢谢！

Answer 1

从中删除22

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

我们用它的顺序后继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

（我正在从这套讲义中工作。不要费心记住这里的细节，除非是为了考试。即便如此...我真的希望数据结构课程不要像他们那样强调平衡的搜索树。