algorithm - AVL 树中的额外案例

Question

AVL 树似乎有四种变换:左-左、左-右、右-左和右-右。但是，似乎也可能存在其他情况。我将其提交为左平衡:

左旋和右旋都不能平衡这棵树。用什么算法来平衡它？

Answer 1

这里LL和LR都可以应用

        50
       /  \
     40    55
    /  \
  35    45
  / \   / \
34  36 44 46

第一次左转后:

           50
          /  \
        45   55
       /  \
     40    46
    /  \
  35    44
  / \
34  36

第二个左转后:

        45
       /  \
     40    50
    / \    / \
  35  44  46  55
 / \
34  36

这是有效的 AVL 树。注意

In an AVL tree, the heights of the two child subtrees of any node differ by at most one

你也可以做 LL 转弯:

     40
    /  \
  35    50
  / \   / \
34  36 45  55
       /\
     44  46

这也是有效的 AVL 树。