Hey Guys, here is my solution : we can use AVL trees for this. We will use the left over space in the bins as the node value. Since we hv N bins and inserting 1 element in the AVL tree takes log(N) time , so inserting N elements will take n*log(N) time. So, AVL tree construction will take N*log(N) time(it will be lesser than this, a little thought will reveal u that. But even if we take n*log(N), we can solve the problem in N*log(N) time). Now we have to search the first node having node value i.e left over space greater than the given value V.
here is the structure for the node: typedef int Element; struct node; typedef struct node avlNode; typedef avlNode *AvlTree; struct node{ Element root; int bucket_number; AvlTree left; AvlTree right; int weight; // required for update operation after insertion and deletion }; here is the algo for searching: int find() //appropriate arguements are passed { if root < V go to right sub tree else { if (node->bucket_number < k) // k is a global variable which holds the bucket number of the bin having the smallest bucket number which can //hold the value V { k=node->bucket_number } first go to left sub tree then go to right sub tree } } It is clear that the time complexity of the whole process is O(n*log(n)) If anybdy has any doubt, feel free to comment Thanks and Regards, Ankit On Mon, May 16, 2011 at 9:37 PM, anshu mishra <anshumishra6...@gmail.com>wrote: > void query(int w, int s, int e, int node) > { > if (s==e) > { > tree[node] -= w; > prpogateNewMax(node); > > return; > } > mid = (s+e)>>1; > if (tree[(node<<1)+1] > = w) query(w, s, mid, (node<<1)+1); > else query(w, mid+1, e, (node<<1)+2); > } > > void prpogateNewMax(int node) > { > if (node == 0) return; > int par = (node-1)>>1; > int a = tree[(par<<1)+1]; > int b = tree[(par<<1)+2]; > > tree[par] = a > b ? a : b; > > prpogateNewMax(par); > } > > Now I think everything is clear. For a single query we have traverse from > root to leaf than leaf to root. total 2*log(n); So finally for n queries > order will be O(n*logn); > > -- > 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. > -- 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.