multiple AVL tree rotation

Question

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:

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?

Chris Frederick Chris Frederick · Accepted Answer · 2011-06-12T19:06:01

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

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.

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

Does that make sense?

multiple AVL tree rotation

1 Answers