多个AVL树旋转 [英] multiple AVL tree rotation

问题描述

说我有一个无序的集合{3,6,5,1,2,4}，我需要构建一个AVL树，

这很好...我理解基本轮到我这里：

  5 
 / \ 
 2 6 
 / \ 
 1 3 
  

但是当我尝试插入4
，我得到我的最终答案（左边的）

  4但实际的答案是：3 
 / \ / \ 
 2 5 2 5 
 / \ \ / / \ 
 1 3 6 1 4 6 
  

当我打破它，我被卡住做同样的旋转，
所以我要求h我和父母对这个AVL有效吗？

我的解决方案是否有效？

解决方案

嗯，据了解，当你第一次添加4时，你会得到以下树。

  5 
 / \ 
 2 6 
 / \ 
 1 3 
 \ 
 4 
  

请按照维基百科关于AVL树的文章。因为节点5的平衡因子（注意这在文章中定义）是+2，而节点2的平衡因子是-1，所以首先需要旋转节点2的子树。 / p>

  5 
 / \ 
 3 6 
 / \ 
 2 4 
 / 
 1 
  

接下来，您需要正确地旋转整个树关于节点5）。

  3 
 / \ 
 2 5 
 / \\ 
 1 4 6 
  

这是否有意义？

Say i have a unordered set s{3,6,5,1,2,4} and i need to construct an AVL tree,
this much is fine... i understand basic rotations and i get to this point here:

                               5 
                             /   \
                            2      6
                           / \
                         1     3

but it all falls apart when i try to insert 4 and i get my final answer as (the left one)

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

And when i break it down i get stuck doing the same rotation
so im asking how do i do a rotation with the parent that is valid for this AVL?

and is my solution valid?

解决方案

Well, as I understand it, when you first add 4 you get the following tree.

    5
   / \
  2   6
 / \
1   3
     \
      4

To follow along, refer to Wikipedia's article on AVL trees. Because the balance factor (note that this is defined in the article) of node 5 is +2 and the balance factor of node 2 is -1, you first need to rotate the node 2 subtree left.

      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?

这篇关于多个AVL树旋转的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！