AVL Tree Balancing

Question

Given the AVL tree below:

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

Is it possible to simply make one rotation of 40, to the right? Do it something like this:

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

It still matches the AVL property, which has - + 1 compared to the left subtree.

In the answer, it performs a double rotation, so the subtree at 35 above will look like this:

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

I don’t understand when to do double rotation and when to do one rotation, if both of them do not violate the height property.

Answer 1

Double rotation may be associated with the use of a specific AVL algorithm. Both answers look like valid AVL trees to me.

Answer 2

If the original question was asked only with an unbalanced AVL tree (and not with a balanced tree before adding or removing a node), then the only reason is the correct answer.

If the question contains an AVL tree before and after adding or removing a node, then the rebalancing algorithm can lead to double rotation.

Answer 3

Both answers are correct, although according to the literature I use:

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

The following characteristic of rotation types is obtained:

• LL: N is inserted into the left subtree of the left subtree A
• LR: N inserted in the right subtree of the left subtree A
• RR: N is inserted into the right subtree of the right subtree A
• RL: N is inserted into the left subtree of the right subtree A

According to these rules, the closest ancestor whose balance factor is 2 is 40 in your example, and the insert was made in the left subtree of the left subtree 40 , so you need to perform LL rotation. Following these rules, the first of your answers will be the selected operation.

However, both answers are correct and depend on the algorithm used and the rules that it follows.