When you say that checking if any of the ancestors is O(n log n) are you assuming that the tree is balanced? It wouldn't be O(n log n) if the tree degenerates into a linked list, would it? So what is your justification in assuming balance?
Dave On Aug 30, 6:01 pm, Ramaswamy R <[email protected]> wrote: > To begin with I find the invariant doesn't hold in the system progressively. > Forget about islock and assume that we only do lock / unlock. Given that a > node cannot be locked if any of its descendants / ancestors is locked. It is > never possible for the tree to enter a state where any of the descendant of > a locked node is locked. > > If that invariant holds then all we need to check is if any of the ancestors > are locked, which is O(log n). O(1) would either require hash table (and > O(n) storage) unless we choose to replicate the lock state in all of the > ancestors as well (which is a pretty ugly solution considering what unlock > would have to do). > > If we can supplement the tree node with a lock status and pointer to child > (only used while unlocking) which is locked we should be able to do it all > in the asked for complexities :). Ugly but possible. Of course there is an > O(n) extra storage. > > On Sat, Aug 29, 2009 at 11:05 AM, 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) > > -- > Yesterday is History. > Tomorrow is a Mystery. > Today is a Gift! That is why it is called the Present :). > > http://sites.google.com/site/ramaswamyr- Hide quoted text - > > - Show quoted text - --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
