AVL tree

Question

State If True or False. Give reason too

Inserting in an AVL tree with n nodes requires $\Theta \left ( \log n \right )$ rotations

Answer 1

In case of insertion , while inserting in an AVL tree , maximum 1 imbalance will occur hence maximum of two rotations(in case it is LR or RL imbalance)..Hence it is O(1)..

In case of deletion , while deleting in an AVL tree ,we have to fix imbalance at each level in the worst case and max of 2 rotations at each level , so no of rotations that are needed in worst case  =  2logn  = O(logn)..

Hence the given statement should be false.

Comments

We need to search and insert a node right for which we need O(logn) time. constant for rotation?

Answer 2

well I concluded it as follows-

height of AVL tree cannot be more than atmost 1.44logn i.e. O(log n) if there are n nodes. So if for the height (log n) tree is unbalanced, there is need of atleast 1 rotation. similarly for height (log n -1) there is need for 1 rotation.. and so on

so for height (log n)   atleast 1 rotation

for height (log n-1)    atleast  1 rotation

for height (log n-2)    atleast  1 rotation

for height (log n-3)    atleast  1 rotation

.

.

.

.

for height (log n    -n)    atleast  1 rotation

thus total rotations 1+1+1+1+1+1…..+1  =  n 

and average rotations  n/n= 1 (assume this as some constant k)

therefore there can be average of K rotations.

so statement is false