AVL trees balancing

Given an AVL tree below:

        23
       /    \     
   19        35
  /  \      /  \     
 8   20   27    40
               /
             38
             /
            36

Is it ok to just do a single rotation at 40, to the right? Making it something like this:

        23
      /    \     
 开发者_StackOverflow中文版  19        35
  /  \      /  \     
 8   20   27    38
               /  \
             36    40

It still conforms tot he AVL property of having -+1 height compared to the left subtree.

In the answer it does a double rotation so the subtree at 35 above would look like this after:

        23
      /    \     
   19        38
  /  \      /  \     
 8   20   35    40
         /  \
        27  36    

I don't understand when to do a double rotation and when to do a single rotation if they both do not violate the height property.

The double rotation may be due to a specific AVL algorithm in use. Both answers look like valid AVL trees to me.

If the original question was given with only the unbalanced AVL tree (and not the balanced tree before a node was added or removed), then the single rotation is a valid answer.

If the question provides the AVL tree before and after a node was added or removed, then the algorithm for rebalancing could result in the double rotation occurring.

Both answers are right, though according to the literature that I use:

The are four types of rotations LL, RR,LR and RL. These rotations are characterized by the nearest ancestor A, of the inserted node N, whose balance factor becomes 2.

The following characterization of rotation types is obtained:

1. LL: N is inserted in the left subtree of the left subtree of A
2. LR: N is inserted in the right subtree of the left subtree of A
3. RR: N is inserted in the right subtree of the right subtree of A
4. RL: N is inserted in the left subtree of the right subtree of A

According to these rules, the nearest ancestor whose balance factor becomes 2 is 40 in your example, and the insertion was made in the left subtree of the left subtree of 40 so you have to perform an LL rotation. Following these rules, the first of your answers will be the chosen operation.

Still, both answers are correct and depends of the algorithm you are using and the rules it follows.