2 votes 2 votes The worst case time complexity of AVL is tree is better in comparison to binary search tree for Search and Insert Operations Search and Delete Operations Insert and Delete Operations Search, Insert and Delete Operations DS data-structures binary-tree ugcnetcse-dec2012-paper2 avl-tree + – im.raj asked Jun 16, 2016 • edited May 30, 2020 by soujanyareddy13 im.raj 5.4k views answer comment Share Follow See 1 comment See all 1 1 comment reply im.raj commented Jun 16, 2016 reply Follow Share is D the answer? 1 votes 1 votes Please log in or register to add a comment.
Best answer 7 votes 7 votes 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)$. rude answered Jun 16, 2016 • selected Jun 16, 2016 by im.raj rude comment Share Follow See all 2 Comments See all 2 2 Comments reply shivanisrivarshini commented Jun 16, 2016 reply Follow Share 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 0 votes 0 votes rude commented Jun 16, 2016 i edited by rude Jun 16, 2016 reply Follow Share 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. 6 votes 6 votes Please log in or register to add a comment.