algorithm - AVL 树中的额外案例

Question

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

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

Answer 1

LL和LR都可以在这里应用

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

在第一个 LR 转弯后：

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

在第二个 LR 转弯后：

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

这是有效的 AVL 树。注意

在 AVL 树中，任何节点的两个子子树的高度最多相差 1

你也可以做 LL 转弯：

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

这又是有效的 AVL 树。

Answer 2

我认为您无法获得左平衡案例。因为如果你建造了左平衡树，你可能会先得到左左或左右，然后树会旋转并保持平衡。