Re: Depth of a tree?
I have a hierarchical set of data stored in tree format. The tree may or may not be a binary tree ... i.e. each node could have 0 thru N sub-nodes. Now, I need to calculate the length of the longest branch, or otherwise, the depth of the tree. My comp. sci. days are a long way behind me, so does anybody know how this would be calculated? Here is an example of how I would do it in Oracle (assuming you have the tree stored in a table in an Oracle database): create table t ( parent varchar2(20) ,title varchar2(20) ,left number ,right number ) / insert into t values ( null, 'Food', 1, 18 ); insert into t values ( 'Food', 'Fruit', 2, 11 ); insert into t values ( 'Fruit', 'Red', 3, 6 ); insert into t values ( 'Red', 'Cherry', 4, 5 ); insert into t values ( 'Fruit', 'Yellow', 7, 10 ); insert into t values ( 'Yellow', 'Banana', 8, 9 ); insert into t values ( 'Food','Meat', 12, 17 ); insert into t values ( 'Meat' , 'Beef', 13, 14 ); insert into t values ( 'Meat' , 'Pork', 15 , 16 ); select max(depth) from ( select level as depth from t connect by parent = prior title start with parent is null ) The above query returns 4. -- Eddie Awad. http://awads.net/ ~| Logware (www.logware.us): a new and convenient web-based time tracking application. Start tracking and documenting hours spent on a project or with a client with Logware today. Try it for free with a 15 day trial account. http://www.houseoffusion.com/banners/view.cfm?bannerid=67 Message: http://www.houseoffusion.com/lists.cfm/link=i:4:211562 Archives: http://www.houseoffusion.com/cf_lists/threads.cfm/4 Subscription: http://www.houseoffusion.com/lists.cfm/link=s:4 Unsubscribe: http://www.houseoffusion.com/cf_lists/unsubscribe.cfm?user=89.70.4 Donations Support: http://www.houseoffusion.com/tiny.cfm/54
Depth of a tree?
I have a hierarchical set of data stored in tree format. The tree may or may not be a binary tree ... i.e. each node could have 0 thru N sub-nodes. Now, I need to calculate the length of the longest branch, or otherwise, the depth of the tree. My comp. sci. days are a long way behind me, so does anybody know how this would be calculated? An example tree I have been working with is as follows ... +++--+---+ | parent | title | left | right | +++--+---+ || Food | 1 | 18 | | Food | Fruit | 2 | 11 | | Fruit | Red| 3 |6 | | Red| Cherry | 4 |5 | | Fruit | Yellow | 7 | 10 | | Yellow | Banana | 8 |9 | | Food | Meat | 12 | 17 | | Meat | Beef | 13 | 14 | | Meat | Pork | 15 | 16 | +++--+---+ So, in this case, the depth would end up being 4 ... Food, Fruit, Red, Cherry - or - Food, Fruit, Yellow, Banana. Any ideas? Thanks -- Jeff ~| Logware (www.logware.us): a new and convenient web-based time tracking application. Start tracking and documenting hours spent on a project or with a client with Logware today. Try it for free with a 15 day trial account. http://www.houseoffusion.com/banners/view.cfm?bannerid=67 Message: http://www.houseoffusion.com/lists.cfm/link=i:4:211513 Archives: http://www.houseoffusion.com/cf_lists/threads.cfm/4 Subscription: http://www.houseoffusion.com/lists.cfm/link=s:4 Unsubscribe: http://www.houseoffusion.com/cf_lists/unsubscribe.cfm?user=11502.10531.4 Donations Support: http://www.houseoffusion.com/tiny.cfm/54
Re: Depth of a tree?
The left/right fields seem to be for nested sets, right? Something like this will work: SELECT MAX(c) FROM ( SELECT COUNT(t2.title) as c FROM fruit t1 INNER JOIN fruit t2 where t2.left = t1.left and t2.right = t1.right GROUP BY t1.id ) t On another note, there's no need to record the parent field in the table, it's computable from the left/right values, and is an instance of [potentially troublesome] denomalization. cheers, barneyb On 7/10/05, Jeff Chastain [EMAIL PROTECTED] wrote: I have a hierarchical set of data stored in tree format. The tree may or may not be a binary tree ... i.e. each node could have 0 thru N sub-nodes. Now, I need to calculate the length of the longest branch, or otherwise, the depth of the tree. My comp. sci. days are a long way behind me, so does anybody know how this would be calculated? An example tree I have been working with is as follows ... +++--+---+ | parent | title | left | right | +++--+---+ || Food | 1 | 18 | | Food | Fruit | 2 | 11 | | Fruit | Red| 3 |6 | | Red| Cherry | 4 |5 | | Fruit | Yellow | 7 | 10 | | Yellow | Banana | 8 |9 | | Food | Meat | 12 | 17 | | Meat | Beef | 13 | 14 | | Meat | Pork | 15 | 16 | +++--+---+ So, in this case, the depth would end up being 4 ... Food, Fruit, Red, Cherry - or - Food, Fruit, Yellow, Banana. Any ideas? Thanks -- Jeff -- Barney Boisvert [EMAIL PROTECTED] 360.319.6145 http://www.barneyb.com/ Got Gmail? I have 50 invites. ~| Logware (www.logware.us): a new and convenient web-based time tracking application. Start tracking and documenting hours spent on a project or with a client with Logware today. Try it for free with a 15 day trial account. http://www.houseoffusion.com/banners/view.cfm?bannerid=67 Message: http://www.houseoffusion.com/lists.cfm/link=i:4:211515 Archives: http://www.houseoffusion.com/cf_lists/threads.cfm/4 Subscription: http://www.houseoffusion.com/lists.cfm/link=s:4 Unsubscribe: http://www.houseoffusion.com/cf_lists/unsubscribe.cfm?user=89.70.4 Donations Support: http://www.houseoffusion.com/tiny.cfm/54
RE: Depth of a tree?
Basically, this is being modeled in a modified pre-order tree traversal where the left and right numbers come from traversing the edges of the tree. The number of descendants for a given node would result from the calculation, (right - left - 1) / 2 ... so, (18 - 1 - 1) / 2 = 8 descendants from the root node. I should have specified before, but this tree/table is actually in a 2-dimensional array format, so queries are not really usable. Either way, it would appear that the query you specified would calculate the total number of nodes in the tree (9), not the depth of the tree(4). What I am trying to find is the length of the longest branch of the tree, and short of writing a recursive function, I am not sure how else to calculate this. Thanks -- Jeff -Original Message- From: Barney Boisvert [mailto:[EMAIL PROTECTED] Sent: Sunday, July 10, 2005 4:38 PM To: CF-Talk Subject: Re: Depth of a tree? The left/right fields seem to be for nested sets, right? Something like this will work: SELECT MAX(c) FROM ( SELECT COUNT(t2.title) as c FROM fruit t1 INNER JOIN fruit t2 where t2.left = t1.left and t2.right = t1.right GROUP BY t1.id ) t On another note, there's no need to record the parent field in the table, it's computable from the left/right values, and is an instance of [potentially troublesome] denomalization. cheers, barneyb On 7/10/05, Jeff Chastain [EMAIL PROTECTED] wrote: I have a hierarchical set of data stored in tree format. The tree may or may not be a binary tree ... i.e. each node could have 0 thru N sub-nodes. Now, I need to calculate the length of the longest branch, or otherwise, the depth of the tree. My comp. sci. days are a long way behind me, so does anybody know how this would be calculated? An example tree I have been working with is as follows ... +++--+---+ | parent | title | left | right | +++--+---+ || Food | 1 | 18 | | Food | Fruit | 2 | 11 | | Fruit | Red| 3 |6 | | Red| Cherry | 4 |5 | | Fruit | Yellow | 7 | 10 | | Yellow | Banana | 8 |9 | | Food | Meat | 12 | 17 | | Meat | Beef | 13 | 14 | | Meat | Pork | 15 | 16 | +++--+---+ So, in this case, the depth would end up being 4 ... Food, Fruit, Red, Cherry - or - Food, Fruit, Yellow, Banana. Any ideas? Thanks -- Jeff -- Barney Boisvert [EMAIL PROTECTED] 360.319.6145 http://www.barneyb.com/ Got Gmail? I have 50 invites. ~| Find out how CFTicket can increase your company's customer support efficiency by 100% http://www.houseoffusion.com/banners/view.cfm?bannerid=49 Message: http://www.houseoffusion.com/lists.cfm/link=i:4:211517 Archives: http://www.houseoffusion.com/cf_lists/threads.cfm/4 Subscription: http://www.houseoffusion.com/lists.cfm/link=s:4 Unsubscribe: http://www.houseoffusion.com/cf_lists/unsubscribe.cfm?user=11502.10531.4 Donations Support: http://www.houseoffusion.com/tiny.cfm/54
Re: Depth of a tree?
No, my query will compute the number of nodes from the root to each individual node, and then select the maximum value, which will be the longest path. If you can't use a query, you'll have to do a recursive descent. However, if you're already doing one to populate the left/right fields, can you just compute it then? cheers, barneyb On 7/10/05, Jeff Chastain [EMAIL PROTECTED] wrote: Basically, this is being modeled in a modified pre-order tree traversal where the left and right numbers come from traversing the edges of the tree. The number of descendants for a given node would result from the calculation, (right - left - 1) / 2 ... so, (18 - 1 - 1) / 2 = 8 descendants from the root node. I should have specified before, but this tree/table is actually in a 2-dimensional array format, so queries are not really usable. Either way, it would appear that the query you specified would calculate the total number of nodes in the tree (9), not the depth of the tree(4). What I am trying to find is the length of the longest branch of the tree, and short of writing a recursive function, I am not sure how else to calculate this. Thanks -- Jeff -- Barney Boisvert [EMAIL PROTECTED] 360.319.6145 http://www.barneyb.com/ Got Gmail? I have 50 invites. ~| Logware (www.logware.us): a new and convenient web-based time tracking application. Start tracking and documenting hours spent on a project or with a client with Logware today. Try it for free with a 15 day trial account. http://www.houseoffusion.com/banners/view.cfm?bannerid=67 Message: http://www.houseoffusion.com/lists.cfm/link=i:4:211518 Archives: http://www.houseoffusion.com/cf_lists/threads.cfm/4 Subscription: http://www.houseoffusion.com/lists.cfm/link=s:4 Unsubscribe: http://www.houseoffusion.com/cf_lists/unsubscribe.cfm?user=11502.10531.4 Donations Support: http://www.houseoffusion.com/tiny.cfm/54
