Jump to content
  • Advertisement

Archived

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

jtech

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.

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
Advertisement
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
All I want is a balanced tree (the tree is not binary), and Red-Black,
Splay trees are for binary trees only.

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!