在 avl 树上执行旋转

Question

有谁知道如何在这棵 avl 树上执行右左旋转？

我将 45 向上移动为根，将 50 向上移动为右子节点，将 40 向上移动为左子节点，但是 45 的子节点去哪里了？任何帮助将不胜感激。

Answer 1

这是树：

           _ 40 _
          /      \
        30        50
       /  \      /  \
     20    35  45    60
              /  \     \
            41    46    70
              \
               42

根部不平衡，并且在重（右侧）侧，内孙子（45）高于外孙子（60），因此需要两次旋转。首先向右旋转 50，向上抬起 45：

           __ 40 __
          /        \
        30        _ 45 _
       /  \      /      \
     20    35  41        50
                 \      /  \
                  42  46    60
                              \
                               70

然后向左旋转 40，再次抬起 45：

           _ 45 _
          /      \
        40        50
       /  \      /  \
     30    41  46    60
    /  \     \         \
  20    35    42        70

就是这样。