5 votes 5 votes 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) DS data-structures avl-tree time-complexity + – srestha asked Jan 16, 2017 retagged Jul 6, 2022 by Lakshman Bhaiya srestha 5.7k views answer comment Share Follow See 1 comment See all 1 1 comment reply Rahul Jain25 commented Jan 16, 2017 reply Follow Share Should be A) 0 votes 0 votes Please log in or register to add a comment.
7 votes 7 votes Elements are present in array which satisfies min heap property so we have to take element from array and construct the AVL tree one by one. Deletion of element from given array takes O(log n) time because it is min heap and for insertion in AVL worst case will be O(log n) time . For n elements Total time= O(nlogn) + O(nlogn) = O(nlogn) Ashwani Kumar 2 answered Jan 16, 2017 Ashwani Kumar 2 comment Share Follow See all 2 Comments See all 2 2 Comments reply cse23 commented Jan 17, 2017 reply Follow Share it should be O(nlogn) deletion will takeO(logn) time as array satisfies the min heap(build the min heap in O(1)) no need of heapify becoz array is already a min heap so simply make a tree so from given array we will delete the element one by one (for n element deletion will take upto O(nlogn)) then insert the element in a tree hence total time will be O(nlogn).....n elements are inserted one by one and in worst case for each insertion we may have to perform O(logn) rotation so construction of AVL will take O(nlogn) + O(nlogn) = O(nlogn) 2 votes 2 votes Mahima Manik commented Jan 23, 2017 reply Follow Share Can we just sort the given array in O(n log n) time and then create AVL tree from the sorted array by making the middle element of the tree as root everytime. It will again take O(n) time for tree construction. Total time = O(n log n) + O(n) = O(n log n) 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes The array is given which satisfies Min-Heap property. We will sort the array using any sorting which takes minimum time i.e. nlog n. Now we recursively compute mid = (start+last)/2; and make the element A[mid] as the root and call the same recursive function on left and right part. AVL tree will be constructed in n.log n time. umang_16 answered Oct 23, 2016 umang_16 comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments umang_16 commented Oct 23, 2016 reply Follow Share @KISHALAY DAS No, we don't need to do any rotation. We are just supposed to construct from the given data. It depends on us how we deal with that part. Ain't it ? 0 votes 0 votes KISHALAY DAS commented Oct 23, 2016 reply Follow Share Yes that's why it is giving less time.If we directly insert element from min heap to AVL tree i think it would be right skewed.Then many rotations will be there and Time would be O(n^2). 0 votes 0 votes umang_16 commented Oct 23, 2016 reply Follow Share Yes. Then it will take more time. 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes A. O(nlogn) For n elements, whatever the given sequence of these elements be (sorted, reverse sorted, unsorted, min/max heap,etc), AVL creation time will be same as creation procedure does not depends upon the sequence of input elements. manikantsharma answered Oct 15, 2020 manikantsharma comment Share Follow See 1 comment See all 1 1 comment reply Jazz_394 commented Jan 19, 2021 reply Follow Share If the array is sorted, we can apply binary search and recursively add the mid element to the root of avl then follow recursively with subtrees ... won't it take only logn time to build the avl tree? 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes array is given which satisfies min heap we will built the tree from the array which takes O(n) time then balancing of the node will take O(logn) time as rotation takes O(1) time to built the AVL and in worst case we can do O(logn) rtation cse23 answered Jan 16, 2017 cse23 comment Share Follow See all 2 Comments See all 2 2 Comments reply srestha commented Jan 16, 2017 reply Follow Share what is ur answer? 0 votes 0 votes Rahul Jain25 commented Jan 16, 2017 reply Follow Share @cse23 I dont think so bcoz it is a heap consider scenario where 1 is at root and 87 is left child where 2 is right child. Still can you balance it and covert it to AVL which is balanced binary tree, definately not. My approach is insert elements one after other from array each will take only log n time so O(n logn). 0 votes 0 votes Please log in or register to add a comment.