2

假设我有一个无序集 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 有效的父级进行旋转?

我的解决方案有效吗?

4

1 回答 1

2

好吧,据我了解,当您第一次添加 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?

于 2011-06-12T19:06:01.053 回答