#### Archived

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

# Trees and depth

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

## 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 on other sites
If it''s a tree, then you just find the node with no parent - the weights are irrelevant. Perhaps you were thinking of a graph?

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

##### 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 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 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 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 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 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 on other sites
I think you''re more confused than I am.

##### Share on other sites
All I want is a balanced tree (the tree is not binary), and Red-Black,
Splay trees are for binary trees only.

1. 1
2. 2
3. 3
Rutin
14
4. 4
5. 5

• 12
• 15
• 9
• 14
• 10
• ### Forum Statistics

• Total Topics
632655
• Total Posts
3007674
• ### Who's Online (See full list)

There are no registered users currently online

×