Archived

This topic is now archived and is closed to further replies.

Trees and depth

This topic is 5767 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Given an arbitrary tree (not necessarily binary) that has nodes with random weights (e.g. distances from each other), how would I find the root or center node? This would ideally minimize the height of the tree.

Share this post


Link to post
Share on other sites
You''re probably right.

Ok, if I picked a random node on this graph, how would I know if this was
the root node of the graph? Let''s just say I forgot about weights for a moment,
and just looked at the depths from this node. I could probably do it by
looping through all nodes and assign each one root, and traverse the entire
graph for each one, so in the end, I would know which one is the best pick,
but that would be too time consuming if I have a lot of nodes.

Share this post


Link to post
Share on other sites
Well, technically a graph has no root - you could start anywhere on the graph. So I think that when you say "root" you mean "a chosen node which minimises the distances to all other nodes"?

I have no idea, not being big on algorithms, but maybe a "minimum spanning tree" is what you''re after.

[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost ]

Share this post


Link to post
Share on other sites
quote:

you mean "a chosen node which minimises the distances to all other nodes"?



That's what I mean. But I don't think a MST will give me
the center node. I think all it does is create a graph,
which really doesn't say where the center node is.

Basically, I want to keep the graph structure connected how it
already is. Something like that would try to change it.


Edited by - jtech on February 22, 2002 11:33:04 PM

Share this post


Link to post
Share on other sites
Sorry, I know little of graph/tree theory too.

Correction: Yes, I do have a tree, not a graph.

I think the main difference between a tree and a graph is that a
graph can have loops, but a tree cannot. Take any branch of a tree,
and you will eventually come to a leaf. But, follow a path on a graph,
and you could end up going in circles. A MST is a way to convert
a graph to a tree, but I already have a tree, so this step is not needed.

Better if I give an example of what I want to do:

Given this tree structure:

A
\\\
BCD

How would I find out that A is the best root? The relationship
between parent and child can be reversed. So, looking at this, you can
say A has 3 parents B,C,D. Or you can say A has no parent, and 3 children,
B,C,D.

If I pick the best root of my tree, I can optimize my searching routines.

Share this post


Link to post
Share on other sites
Red-black trees and Splay Trees are designed to minimize the height of a tree, though I''ve only used them for binary trees (Splay could probably work on n-ary.. red-black might be a little weird if not impossible to generalize)

They''re for rooted trees though... nodes in a rooted tree only have one parent, so what you describe with A having no children and three parents would be more like a graph... and most algorithms for graphs have pretty poor running times like O(n^2)

Take a look at http://mathworld.wolfram.com/Tree.html and look up other information on Dijkstra''s Algorithm and Dijkstra Trees

...Personally, I''d find a better structure or a new way to optimize your search algorithms

Share this post


Link to post
Share on other sites
The only way you can know if the current node you''re at is the root is:
#1, Each node has a Parent pointer that points to it''s parent, and, if the Parent pointer is NULL, you''re at root.
#2, You have a variable declared Root, and the Node you''re at == Root.


Most implementatoins of trees have a root pointer, and each ndoe only has children pointers. However, it begs the question, how did you get to the node you''re at if you don''t know the root?

Share this post


Link to post
Share on other sites
OK, so you have some random tree, and you want to find the best possible root for that tree?

If it''s a Binary tree, look into B+ Trees, and if its a n-ary tree, look up Dijkstra, Kruskal, and Prim. all 3 of these guys have done alot of research on minimum distances and such.

hope that helps

Waramp.

Share this post


Link to post
Share on other sites
quote:

its a n-ary tree, look up Dijkstra, Kruskal, and Prim. all 3 of these guys have done alot of research on minimum distances and such.



These algo''s don''t find the root...they only find a tree and
give you an arbitrary node as root. They don''t give you the
best root.

With Dijkstra, you have to pick a node to start, it doesn''t
give it to you at the end.

Don''t worry about it. I''m looking into something else.

Share this post


Link to post
Share on other sites
Some of you are looking at the literal description of a tree in memory as being the only description of that tree. Here''s a dumb example:

Think of a 3d model of the hierarchy of joints in a human. The root might be the pelvis, and everything else is a descendant of the pelvis. So the literal description to the program has the pelvis as being the root.

But any tree can be viewed from any node as being the root. What jtech wants is to be able to find which node optimizes tree depth to the minimum.

Back to the human model. We could easily view the left big toe as the parent, and everything connected to that as being a descendant. This in fact would be very handy if we were doing a calculation with the big toe rooted to the floor.

Anyway, any tree can be viewed with any node as the root.

Share this post


Link to post
Share on other sites
This may work:

Start at the existing parent and traverse the tree. When you get to the leaves, return back, saving maximum descendant distance at each node.

Now, traverse the tree again from the root. Take the maximum descendant distance of the root with you to each node, adding in the maximum distance to the maximum descendant distance saved at that node and the distance traversed to that node. That number should give you the maximum depth for that node if it was the root. Touch all of the nodes. Choose the one with the least total.

Share this post


Link to post
Share on other sites
Ok, let me try to follow your logic.

Given this tree, with all distances equal from node to node, say 1 unit:

  
B
|
E - A - C
|
D


A is obviously the best choice, but let''s make D root.

If I record all distances from D:
D to A = 1
D to B = 2
D to C = 2
D to E = 2

D has one branch with max dist of 2.

Now traverse again, and add the max dist to all nodes:

D to A = 1 + 2 = 3
D to B = 2 + 2 = 4
D to C = 2 + 2 = 4
D to E = 2 + 2 = 4

3 the the least one, so A is the best root. Does this sound
correct?

Share this post


Link to post
Share on other sites
quote:
Original post by jtech

      
B K
| |
E - A - C G J
| | |
D - - - F - H


Umm, look:

D is the root. Traverse the tree and compute the max chain of descendants at each link.

D -> A = 2
A -> B = 1
A -> E = 1
A -> C = 1
D -> F = 4
F -> G = 1
F -> H = 3
H -> J = 2
J -> K = 1

Now:

Start at D. Traverse the tree again. Start by going to A. D's max depth is D -> F = 4. Carry this to A, which is 1 away, so add 4 to 1, and we get 5. Since 5 is greater than any of A's max depths, which all equal 1, A's true depth is 5.

Keep traversing the tree as above. When we traverse from D to F, don't take the D -> F depth value. Instead, take the greatest of D's other depth values. In this case, it would be D -> A, which equals 2. Add 2 to the distance we traversed from D to F, which is 1. 1 + 2 = 3, which is no greater than F's maximum recorded depth of 3, so we conclude F's true depth is 3.

Keep doing this, and keep track of the node with the smallest value.


___________________________________



Edited by - bishop_pass on February 26, 2002 8:42:03 PM

Share this post


Link to post
Share on other sites
quote:
Original post by WarAmp
If it''s a Binary tree, look into B+ Trees, and if its a n-ary tree, look up Dijkstra, Kruskal, and Prim. all 3 of these guys have done alot of research on minimum distances and such.



Actually, B-Trees are not binary trees, they are m-ary trees where each node can have at most m child nodes, and at least ciel(m/2) child nodes. Except in the case of the root. B-Trees can be really good at minimizing the depth of a tree, and you can gaurantee that all data in the tree will be at the same level.

J.W.

Share this post


Link to post
Share on other sites
ahhh. When I was taught B+Trees, I was told they were for binary, but now that I think of it, I suppose they could easily be extended for m-branches. Thanks for clearing that up.

Waramp.

Share this post


Link to post
Share on other sites

I''m still trying to figure it out

I got the code written to find the max num of descendants for
each node, but the second part is little murky.

Here''s what I got:

  
typedef struct _NODE {

INT num_nodes;
struct _NODE *nodes;

} NODE;


INT
Get_Num_Descendants( NODE *parent, INT parent_depth ) {

if(NULL == parent) {
return parent_depth;
}

INT max=0;
for(INT i=0; i < parent->num_nodes; i++) {

if(parent->nodes[i]) {
INT d = Get_Num_Descendants( parent->nodes[i], (parent_depth+1) );
max = MAX( max, d );
}
}

max = MAX( max, parent_depth );

return max;
}

Share this post


Link to post
Share on other sites