Test Series

Question

Delete the key sequence [6,5,4] from the below AVL tree. How many rotations are needed to make it balanced AVL tree again?

Comments

Only 1 rotation is required.

After deleting [6,5,4] there will be L-L and L-R both imbalances for node 3.

Then L-L will take only 1 rotation and will balance it.

Actually in the question they have to mention about "minimum" word.

the resultant tree -

            1

     0             3

               2

---

Thanks I was having same doubt.

---

i think only 1 rotation are needed...

Answer 1

delete 6 - no rotation is required 

delete 5 - tree will be like           3

                                              1                    4

                                         0         2

          at this point tree is balanced now  delete 4

delete 4  root become unbalanced it will rotate to the right. 

tree will become like :

                                         1

                                  0                    3

                                                  2

So only one rotation is needed.

Answer 2

one right rotation