UGC NET CSE | December 2012 | Part 2 | Question: 2

Question

The worst case time complexity of AVL is tree is better in comparison to binary search tree for

• A. Search and Insert Operations
• B. Search and Delete Operations
• C. Insert and Delete Operations
• D. Search, Insert and Delete Operations

Comments

is D the answer?

Answer 1

Correct Answer would be D) Search, Insert and Deletion operation
 

Because Search is $O(\log N)$ since AVL trees are always balanced. Insertion and deletions are also $O(\log n)$ Where as in case of BST it is $O(n)$.

Comments

but while insertion or deletion we need to balance the tree what about rotations in AVL tree

I know search is fast but coming to insertion in BST we just move either left or right and we insert where as in AVL we need to move and we even need to check balancing na wont it take time more han BST

Sorry If anything is wrong in my Doubt Thanks

---

Every doubt is welcome, no problem at all.

See Rotation is not a big task, Thats done in $O(1)$ time only. In the rotations its seems that we are doing something really serious stuf, but actually we are upadating some address only. 

Now come to Insertion:

1) First we have to reach at the point where we will insert the node. $O(log n)$ times. 

2) Insert it. $O(1)$

3) Start calculating balance factor all the parents. untill we did not get the unbalanced node or we reach to root. This will take $O(log n)$ time. 

4) If there is any unbalance node then we need maximum only 2 rotation. $O(1)$ times. 

===> Look at these all the 4 steps, all are happening independent. Hence time complexity of insertion will be $O(log n)$ only. 

Similarly you can carefully observe the time complexity of Deletion also. 

Check that if you could not get then let me know i will explain that.