@Dufus: You mean to say do preprocessing and hash all the nodes that cannot be locked, if am not wrong. And again, Everytime we lock a node, we need to update the hash and that would be O(n) worst case. Can we do anything better ?
--Priya On Sun, Aug 30, 2009 at 10:26 AM, Dufus <[email protected]> wrote: > > 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 <[email protected]> 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 <[email protected] > >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 [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 -~----------~----~----~----~------~----~------~--~---
