How many rotations are required during the construction of an AVL tree if the…
2022
How many rotations are required during the construction of an AVL tree if the following elements are to be added in the given sequence?
35,50,40,25,30,60,78,20,28
- A.
2 left rotations, 2 right rotations
- B.
2 left rotations, 3 right rotations
- C.
3 left rotations, 2 right rotations
- D.
3 left rotations, 1 right rotation
Attempted by 167 students.
Show answer & explanation
Correct answer: C
Final answer: 3 left rotations, 2 right rotations
Insert 35, 50, 40: the tree becomes unbalanced at 35 with a right-left case. Fix by performing a right rotation on 50, then a left rotation on 35.
Rotations so far: 1 left rotation, 1 right rotation.
Insert 25: no rotation required.
Insert 30: causes a left-right case at node 35. Fix by performing a left rotation on 25, then a right rotation on 35.
Rotations accumulated: +1 left, +1 right (running totals: 2 left, 2 right).
Insert 60: no rotation required.
Insert 78: causes a right-right case at node 50. Fix by performing a single left rotation on 50.
Rotations accumulated: +1 left (running totals: 3 left, 2 right).
Insert 20 and 28: these insertions do not cause any further rotations; balance factors remain within allowed range after fixes.
Total rotations: 3 left rotations, 2 right rotations.
Tip: To determine rotations while building an AVL tree, compute the balance factor (height of left subtree minus height of right subtree) after each insertion. If a node's balance becomes +2 or -2, identify the case (left-left, left-right, right-right, or right-left) and apply the appropriate single or double rotations.
A video solution is available for this question — log in and enroll to watch it.