重新平衡AVL树

Question

我有以下AVL树：

       10 
          / \ 
          5  12 
         /\ /\ 
          2 8 11 13 
         /\ /\ 
         1 4 7 9 

如果我插入3然后我得到：

       10 
          / \ 
          5  12 
         /\ /\ 
          2 8 11 13 
         /\ /\ 
         1 4 7 9 
         /
         3 

如果我计算的平衡因子为每个节点似乎每BF是有效的： （节点：BF）→10：1,5：0,2：-1,1：0,4：-1,8：0,7：0,9：0,3：0,12 ：0，11：0,13：0 但显然这棵树需要重新平衡。哪里有无效的BF，然后怎么去做必要的旋转。

Answer 1

10应该有一个平衡因子2与它的左子树5-2-4-3及其右子树12-13。一次旋转后的有效树可能看起来像5 | 2 10 | 1 4 8 12 | nil nil 3 nil 7 9 11 13.

一种可能的重新平衡方法是切割链接算法： 1.将非平衡节点z命名为它的一个子节点y和它的一个子节点x。 2.将节点重命名为a，b，c inorder-traversal，并让其子节点从左到右依次为T0，T1，T2和T3。 3.将b设置为新的根，a作为其左侧的孩子，c作为其右侧的孩子。 4.将从左到右对应的四个子树追加为T0，T1，T2和T3。