As suggested in the question keep an m-bit structure in each node. If the i-th bit is set to 1 then node pointed to (i + 1)th pointer cannot be locked. The key idea is to do this recursively ( i.e) once a node is locked all the bits in its m-bit structure get set. Over and above this all the nodes that were used to get to this node must also be modified, but how, this is easy with recursion or even an explicit stack is not that hard. Here it is important to set that bit whose corresponding pointer led to node getting locked. That is, if in level 1 (root) the (k + 1)th pointer was followed to get to node N then kth bit is set and at level 2 if (r + 1)th pointer was followed to then r-th bit is set and so on. Now to check if a node X can be locked start from root and follow the pointer that leads to X, if that is set then X cannot be locked. Apply this recursively.
Cheers,
Padmanabhan
On 3/25/06, ridvansg <[EMAIL PROTECTED]> wrote:
--~--~---------~--~----~------------~-------~--~----~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
