Aspire's Library

A Place for Latest Exam wise Questions, Videos, Previous Year Papers,
Study Stuff for MCA Examinations - NIMCET

Previous Year Question (PYQs)



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$





Solution

Insert elements one by one in AVL tree.

Insert $35$:

Tree is balanced. No rotation.

Insert $50$:

$50$ becomes right child of $35$.

Tree is balanced. No rotation.

Insert $40$:

$40$ goes to left of $50$.

This creates Right-Left imbalance at $35$.

For Right-Left case, we do:

Right rotation at $50$

Left rotation at $35$

So far:

Left rotations $=1$

Right rotations $=1$

Insert $25$:

$25$ goes to left side.

Tree remains balanced. No rotation.

Insert $30$:

$30$ goes to right of $25$.

This creates Left-Right imbalance at $35$.

For Left-Right case, we do:

Left rotation at $25$

Right rotation at $35$

Now total:

Left rotations $=2$

Right rotations $=2$

Insert $60$:

$60$ goes to right side.

Tree remains balanced. No rotation.

Insert $78$:

$78$ goes to right of $60$.

This creates Right-Right imbalance at $50$.

For Right-Right case, we do:

Left rotation at $50$

Now total:

Left rotations $=3$

Right rotations $=2$

Insert $20$:

$20$ goes to left side.

Tree remains balanced. No rotation.

Insert $28$:

$28$ goes to right of $25$.

Tree still remains balanced. No rotation.

Therefore, total rotations are:

$3$ left rotations and $2$ right rotations.


Online Test Series,
Information About Examination,
Syllabus, Notification
and More.

Click Here to
View More


Online Test Series,
Information About Examination,
Syllabus, Notification
and More.

Click Here to
View More

Ask Your Question or Put Your Review.

loading...