@Ankit
Wht about updating the nodes when a value has been added to the
bin ??
The left over space has to be modified n so is the tree.
On May 17, 1:17 pm, ankit sambyal <ankitsamb...@gmail.com> wrote:
> 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.
