retagged by
1,999 views
5 votes
5 votes

Which of the following is highest upper bound that represents the time complexity of inserting an object into AVL tree with n-nodes.


It must be 0(logn) right.

What would be answer if it asked that element is continuously inserting in to a AVL tree.

retagged by

1 Answer

0 votes
0 votes

So, if we have n nodes in the AVL tree and we add one more number it will take O(logn) time to insert it. AVL trees balanced binary tree so at any point of time AVL tree will have a height of O(h) (where h=logn).

When we insert any node to the AVL tree following are the steps to be taken.

1. Find the appropriate place of insertion .(i.e do a binary search to get the location to insert element, as it is already sorted it will take O(logn) time.

2. Updating the height (it takes constant time )

3. Rotations  (it also takes constant time, as we have to just update some pointers)

 

Now, if we want to add m more nodes to the tree it will take another m insertions and time complexity for each insertion would be:- 

  $log(n+1) + log(n+2)+ log(n+3)+ .....+log(n+m)$ 

 =$log((n+1)*(n+2)*(n+3)*....* (n+m-1)*(n+m))$

=$log ( (n+m)! /(n!))$

=$(n+m) log(n+m)- nlogn$

=$O((n+m) log (n+m))$

edited by

Related questions

1 votes
1 votes
4 answers
1
GateAspirant999 asked Apr 23, 2016
3,745 views
The tree given is as follows: 40 / \ 35 53 / \ 20 60 How many rotations are required for insertion of elements 30,55,45,6...
5 votes
5 votes
4 answers
2
srestha asked Jan 16, 2017
5,747 views
What is the worst case time complexity to construct an AVL tree from an array which satisfies the min heap property ?a) O(n log n)b) O(n2)c) O(n2 log n)d) O(n)
1 votes
1 votes
0 answers
3
Chaitanya Kale asked Oct 9, 2022
391 views
Given a skew tree what will be the time complexity to balance the tree? What will be the algorithm for this?
0 votes
0 votes
1 answer
4
Arnabi asked Jan 28, 2017
725 views