AVL Tree

Question

Suppose we have an AVL tree of n nodes and any change in the tree violates the AVL tree property then :-
S1: If we insert an element in the tree, maximum 2 Rotations are required to make the Tree AVL again.
S2: If we delete an element from the tree, maximum 2 Rotations are required to make tree AVL again

Which are correct statements?

Comments

yes both false

https://stackoverflow.com/questions/20912461/more-than-one-rotation-needed-to-balance-an-avl-tree

---

RL , LR 1 rotation
So, 1 rotation for insertion atmost

---

@ srestha  i checked your link. For insertion when we need to do LR it means 1st RR is done then LL. It is a two step rotation process right? Why atmost 1 then?

Answer 1

its depends on tree height

Answer 2

For insert 1 rotation is at most.
For delete the number of rotation is bounded by O(log(n)). Log(n) is the height of the tree.
More explanation on AVL deletion. When you delete a node from AVL you might cause the tree unbalanced, which you have to trace back to the point where it is unbalanced. If the unbalanced point is the root. You have to rebalance the tree from top to bottom.

Both false.

Ref: https://stackoverflow.com/questions/20912461/more-than-one-rotation-needed-to-balance-an-avl-tree

Answer 3

RL= LL+RR and LR=RR+LL.   So for insertions max 2 rotations (ie RR or LL or both) can be done but in case of deletion max 1 rotation (either RR or LL) is sufficient.  So S1 is true and S2 is false