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 <shashank7andr...@gmail.com>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 algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
