The number of rotations required to insert a sequence of elements 9,6,5,8,7,10…
2013
The number of rotations required to insert a sequence of elements 9,6,5,8,7,10 into an empty AVL tree is?
- A.
0
- B.
1
- C.
2
- D.
3
Attempted by 306 students.
Show answer & explanation
Correct answer: D
1. Insert 9: Root is 9.
2. Insert 6: Left of 9. No rotation.
3. Insert 5: LL imbalance at 9. Right rotation on 9 (1st rotation). Tree becomes Root 6, Left 5, Right 9.
4. Insert 8: Right of 6, Left of 9. No rotation.
5. Insert 7: LL imbalance at 9. Right rotation on 9 (2nd rotation). Tree becomes Root 6, Left 5, Right 8.
6. Insert 10: RR imbalance at 6. Left rotation on 6 (3rd rotation). Total rotations required is 3.