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 <[email protected]>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 [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.
