Priya, as mentioned by you your isLock() takes O(logn) time.
We need to use Hash table as auxillary DS for O(1) query time.
_dufus
On Aug 30, 8:35 am, priya k <priya.annau...@gmail.com> wrote:
> // Data Structure for the n-ary tree
>
> struct node
> {
> int data;
> node * child[m];
> bool lockFlag; // Indicates if a node is locked or not
> node *parent; //Holds the immediate parent of the node
> int LockCount; //Holds how many nodes arrested this node
>
> };
>
> // Takes logm(N) in the worst case
>
> bool check(node *NodeToBeLocked)
> {
> node *m=NodeToBeLocked;
>
> if(m->flag==true || m->LockCount>0)
> return false; // since the node is already locked or any of its
> subtrees already locked, return false
>
> while(m && !m->lockFlag)
> m=m->parent;
>
> if(m && m->lockFlag)
> return false; // if any of its ancestors have been already locked
>
> return true;
>
> }
>
> // Takes logm(N) in the worst case
>
> bool lock(node *NodeToBeLocked)
> {
> if(check(NodeToBeLocked)) // If true, Node is free to be locked
> {
> node *m=NodeToBeLocked;
> m->lock=true;
> node *prevChild=m;
> m=m->parent;
> while(m)
> {
> m->LockCount++;
> prevChild=m;
> m=m->parent;
> }
> return true;
> }
> return false; //err.. cannot be locked
>
> }
>
> // Takes logm(N) in the worst case
>
> bool unlock(node *NodeToBeUnLocked)
> {
> node *m=NodeToUnBeLocked;
> m->lock=false; // Unlock the Node
> node *prevChild=m;
> m=m->parent;
> while(m)
> {
> m->LockCount--;
> prevChild=m;
> m=m->parent;
> }
>
> }
>
> Thanks,
> Priya
>
> On Sat, Aug 29, 2009 at 11:35 PM, nagendra kumar
> <nagendra....@gmail.com>wrote:
>
>
>
> > Given a n-ary tree of resources arranged hierarchically. A process
> > needs to lock a resource node in order to use it. But,
> > A node cannot be locked if any of its descendant or ancestor is
> > locked.
> > I was supposed to
> > -> write the structure of node
> > -> write codes for
> > -> islock()- returns true if a given node is locked and false if it is
> > not
> > -> lock()- locks the given node if possible and updates lock
> > information
> > -> unlock()- unlocks the node and updates information.
> > Codes should be :
> > Islock –O(1)
> > Lock()- O(log n)
> > unLock()- O(log n)
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
