Test Book- Data Structure Test

Question

In an AVL tree a single insertion can cause how many rotations at a particular time in worst case?

Answer 1

In worst case there will be only 2 rotation.  In best case 0 rotation.

Comments

can u pls explain why ??

---

if after insertion avl tree is not disturbed then 0 rotation required. But if after insertion it is not balanced then it can create either LL or RR or LR or RL problem.   If it ll or rr then only one rotation is required.  But if it is lr or rl then 2 rotation is required.  Since we need to convert them to either ll or rr depending on the problem.  and we can also show that height of the node is not disturbed hence in backtracking there will be no problem.

---

ok got it .. thanks !!

---

asking about tree not single node first of all....

so it should be depend on height .. because  if our avl tree has some height then only not leaf node going to suffer from rotation but we may change also root due to rotation ....

---

2 is never going to be answer

---

@Deepanshu I also thought the same thing.. but they have given the ans as 2...

---

then may be they mistake in question of node and tree because with tree if answer is 2 then it is not making much sense ...

---

then what should be the ans for tree?

---

may be 2 is the right answer ....nice question..
as previous all subtree are all already balanced so  for that tree it is going to affect they are gonna do and at a time i am only getting 1 tree which is out of place so i think maybe 2 but no valid proof just examples from here and there