Its Both of the BST and Heap... Prem
On Tue, Aug 23, 2011 at 5:01 PM, sagar pareek <[email protected]> wrote: > I m surprised that ur whole explanation is for me :-o > Check ur previous post and then last post... > i think u r confused > > > On Tue, Aug 23, 2011 at 3:10 PM, WgpShashank > <[email protected]>wrote: > >> @sagar, >> >> A self-balancing balancing binary search tree(Its *BST not BT )*containing n >> items allows the lookup, insertion, and removal of an item in >> O(log n) worst-case time. Since it’s a BST, we can easily find out minimum >> element in O(nlogn). please note that if it would have been simple BST not >> Balnced BST then our complexity to lookup will changes to O(n) in worst case >> when tree is skewed but as question say balanced BST (check out AVL/RB Tree) >> they gureentte that look-up will O(logn) only why its true & will work you >> need to go through tree rotation (thats used to make tree balanced & reduce >> height ). >> >> Since Heap is a balanced binary tree (or almost complete binary tree but >> not balanced BST ), insertion complexity for heap is O(logn). Also >> complexity to get minimum in a min heap is O(logn) because removal of root >> node causes a call to >> heapify<http://www.cs.virginia.edu/%7Eluebke/cs332.fall00/lecture4/index.htm>(after >> removing the first element from the array) to maintain the heap tree >> property. But a heap cannot be used for the above purpose as the question >> says – insert an element if it is not already present because of this >> constraint we can't use min-heap as well . For a heap, we cannot find out in >> O(logn) if an element is present or not as its balanced Binary Tree(BT) , we >> have to search all the elements e.g.in both left & right sub-tree up-to >> leaf so in worst case it will take O(n) time to search an element weather >> ist present or not , then its present leave it else insert as a last node & >> call heapify (take O(logn)) so tottal time complexity will be O(n)+ O(logn) >> =O(n) >> >> search+heapify =O(search) >> >> so why correct answer is only Balanced Binary Search Tree >> >> Do Notify me if i missed something or wants more clarification ? >> >> >> *Thanks >> Shashank Mani >> Computer Science >> Birla Institute of Technology Mesra* >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To view this discussion on the web visit >> https://groups.google.com/d/msg/algogeeks/-/65k0xGJY6ZoJ. >> >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > > > -- > **Regards > SAGAR PAREEK > COMPUTER SCIENCE AND ENGINEERING > NIT ALLAHABAD > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
