AVL 树中的额外案例

Question

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

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

Answer 1

我认为你不能得到左平衡的情况。因为如果你建的是左平衡的，你可能先得到左-左或左-右，然后树会旋转并保持平衡。

Answer 2

这里LL和LR都可以应用

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

第一次左转后：

第二个 LR 回合后：

        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 树。

Extra Cases in AVL Trees