[algogeeks] Re: n-ary tree
use a linked list to store child nodes, a tree node will hold pointer
to next sibling and a pointer to its first child.
typedef struct TreeNode{
struct TreeNode * nextSibling;
struct TreeNode * fistChild;
//rest things
}
On Aug 6, 4:10 pm, Aman Goyal aman.goya...@gmail.com wrote:
Can anyone suggests a good data structure for n-ary tree.. where n is the
input by the user...
--
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?hl=en.
Re: [algogeeks] Re: n-ary tree
thanks, by no means we can add the child nodes dynamically to the father
node??
On Sat, Aug 6, 2011 at 5:33 PM, rohit q.ro...@gmail.com wrote:
use a linked list to store child nodes, a tree node will hold pointer
to next sibling and a pointer to its first child.
typedef struct TreeNode{
struct TreeNode * nextSibling;
struct TreeNode * fistChild;
//rest things
}
On Aug 6, 4:10 pm, Aman Goyal aman.goya...@gmail.com wrote:
Can anyone suggests a good data structure for n-ary tree.. where n is the
input by the user...
--
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?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 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?hl=en.
[algogeeks] Re: n ary tree symmetry
On Jun 29, 10:50 pm, sharad kumar sharad20073...@gmail.com wrote:
@gene
i tried but unable to extend it to n ary tree...can u plzz extend it to n
ary ...
thnx in advance..
// check a for symmetry
boolean is1(a)
{
if (a == null) return true;
for (i = 0, j = a-n_children - 1; i j; i++, j--)
if (!is2(a-child[i], a-child[j])
return false;
return i == j ? is1(a-child[i]) : true;
}
// check that pair a and b are mirror images
boolean is2(a, b)
{
if (a == null b == null) return true;
if (a != null b != null a-key == b-key a-n_children == b-
n_children) {
for (i = 0, j = a-n_children - 1; j = 0; i++, j--)
if (!is2(a-child[i], b-child[j])
return false;
return true;
}
return false;
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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?hl=en.
[algogeeks] Re: n ary tree symmetry
On Jun 27, 7:32 am, sharad kumar sharad20073...@gmail.com wrote:
Algorithm to find if a tree is symmetric? (The tree is a generalized tree
with as many child nodes as possible)
Here's how to do it with a binary tree. Extension to an n-ary tree is
straightforward.
boolean is(a, b)
{
if (a == null b == null) return true;
if (a != null b != null a-key == b-key)
return is(a-left, b-right) is(a-right, b-left);
return false;
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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?hl=en.
[algogeeks] Re: N-Ary Tree and Resource management
@ all. how come it is O(log n). It should be order (height) whcih is not the O(log n) unless and until tree is not balanced. On Mon, Aug 31, 2009 at 11:39 AM, Dufusrahul.dev.si...@gmail.com wrote: Rama, I cannot agree with you more here. On Aug 31, 5:34 am, Ramaswamy R ramaswam...@gmail.com wrote: When we talk of a binary search tree having O(log n) complexity for search, that does assume that the tree is fairly balanced. And of course the that fact we talk of average case. For any tree the worst case would be at least O(n). The whole advantage of using a tree in the 1st place lies in the fact that operations can be done in O(log n) in average case. I don't know of any algo that can do it in O(log n) worst case! :) On Sun, Aug 30, 2009 at 5:05 PM, Dave dave_and_da...@juno.com wrote: 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 ramaswam...@gmail.com 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 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) -- 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 - -- 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 --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: N-Ary Tree and Resource management
I thnik the statement is : a node cannot be locked of any of its ancestors and descendents are locked. On Tue, Sep 1, 2009 at 8:21 PM, ankur aggarwalankur.mast@gmail.com wrote: @narendra.. i think ques need to recheck becoz the statement u r giving A node cannot be locked if any of its descendant or ancestor is locked .. should not be A node cannot be locked if any of its ancestor is locked. 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 -~--~~~~--~~--~--~---
[algogeeks] Re: N-Ary Tree and Resource management
Rama, can you explain your O(1) time and additional O(n) space algorithm to check if a node is in a locked state. Trust me it is more difficult then it sounds. _dufus On Aug 31, 4:01 am, Ramaswamy R ramaswam...@gmail.com 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 nagendra@gmail.comwrote: 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 --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: N-Ary Tree and Resource management
@Priya:
How it will come to O(log n). The statement
while(cond)
m=m-parent;
will covers top to bottom in a tree.
whick will be O(n). explain ur logic hoiw is it O(log n).
-Nagendra.
On Sun, Aug 30, 2009 at 11:40 AM, priya kpriya.annau...@gmail.com wrote:
@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 rahul.dev.si...@gmail.com 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 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-LockCount0)
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.comwrote:
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
-~--~~~~--~~--~--~---
[algogeeks] Re: N-Ary Tree and Resource management
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 nagendra@gmail.comwrote: 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 --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: N-Ary Tree and Resource management
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 ramaswam...@gmail.com 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 nagendra@gmail.comwrote: 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 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 -~--~~~~--~~--~--~---
[algogeeks] Re: N-Ary Tree and Resource management
Aargh, silly me :D
I think we can assign a prime number, Prime_i 1 to all the nodes i
in the tree.
Preprocessing : Each node i must maintain a product Pi of all the
prime numbers corresponding to to each of its nodes in the subtree
rooted at node i (including node i). This can be done in O(n) time.
Locking:-
Whenever we lock a particular node i we communicate Pi to the root
node. The root node would keep product (lets call it P, which has
initial value 1) which would be basically product of Pi of all the
nodes i which have been locked. O(1) time.
We also tag each of the ancestor node j of i with value Vj = 2 (a code
which would indicate that a node cannot be locked because one of its
descendent has been locked)...and increment the value lock_count, LCj
(which is initially 0) to indicate how many of its descendent have
been locked O(logn) time.
Tag the node i with value Vi = 1 ( a code which would indicate that
node i has been explicitly locked).
Unlocking:-
Whenever we unlock a particular node i we set the root node's P = P/
Pi. O(1) time.
And decrement lock_count for all of the ancestor nodes j of node i
(LCj--)
If LCj == 0 reset Vj = 0 indicating that no descendent of node j is
currently locked.
Querying:-
To check if node i is currently in a locked set.
Check Vj.
If Vj != 0
{
j is locked.
}
Else
Divide P by Prime_i.
{
If remainder == 0 then node i is in a locked state (basically node
i has one of its ancestor/parent explicitly locked).
otherwise node i is in a unlocked state
}
Phewthat was one long post.
I hope I made myself clear.
_dufus
On Aug 30, 4:21 pm, Nagendra Kumar nagendra@gmail.com wrote:
@Dufus.
if d is locked then only b,a,g,h cannot be locked .But
c,f,e,i,j can be locked.
On Sun, Aug 30, 2009 at 1:41 PM, Dufusrahul.dev.si...@gmail.com wrote:
Before I propose my solution I have a query.
Consider the following tree:-
a
/ \
b c
/ \ /
d e f
/ \ /\
g h i j
Initially all the nodes are in unlocked state.
Say user choses to lock node d.
Now by the given condition:-
i) none of its children {g,h} can be locked.
ii) none of the nodes which have d as child (ie. ancestors of d) can
be locked which are {b,a} // Since a node i cannot be locked if any of
its descendant is already locked.
Also note that a is ancestor of all the nodes in the tree, we end up
locking the WHOLE TREE (i.e. once d is locked no other node in the
tree can be locked)!!!
I think something is wrong here.
Nagendra/Priya any comments?
_dufus
On Aug 30, 11:10 am, priya k priya.annau...@gmail.com wrote:
@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 rahul.dev.si...@gmail.com 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 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-LockCount0)
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
[algogeeks] Re: N-Ary Tree and Resource management
When we talk of a binary search tree having O(log n) complexity for search, that does assume that the tree is fairly balanced. And of course the that fact we talk of average case. For any tree the worst case would be at least O(n). The whole advantage of using a tree in the 1st place lies in the fact that operations can be done in O(log n) in average case. I don't know of any algo that can do it in O(log n) worst case! :) On Sun, Aug 30, 2009 at 5:05 PM, Dave dave_and_da...@juno.com wrote: 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 ramaswam...@gmail.com 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 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) -- 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 - -- 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 --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: N-Ary Tree and Resource management
// 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-LockCount0)
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.comwrote:
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
-~--~~~~--~~--~--~---
