data-structures - 多个 AVL 树旋转

Question

假设我有一个无序集 s{3,6,5,1,2,4}，我需要构建一个 AVL 树，
这很好......我了解基本旋转，我在这里达到这一点：

                               5 
                             /   \
                            2      6
                           / \
                         1     3

但是当我尝试插入 4 并且我得到最终答案时，一切都崩溃了（左侧）

             4      But the actual answer is:      3
           /   \                                 /   \
          2     5                               2     5
         / \     \                             /     / \
        1   3     6                           1     4   6

当我分解它时，我会卡在做同样的旋转
，所以我问我如何与对这个 AVL 有效的父级进行旋转？

我的解决方案有效吗？

Answer 1

好吧，据我了解，当您第一次添加 4 时，您会得到以下树。

    5
   / \
  2   6
 / \
1   3
     \
      4

要继续进行，请参阅Wikipedia 关于 AVL 树的文章。因为节点5的平衡因子（注意这是在文章中定义的）为+2，节点2的平衡因子为-1，所以首先需要将节点2的子树向左旋转。

      5
     / \
    3   6
   / \
  2   4
 /
1

Next, you need to rotate the entire tree right (about node 5).

    3
   / \
  2   5
 /   / \
1   4   6

Does that make sense?