Multi-Root Tree Structure

Question

I have a data such that there are many parents each with 0-n children where each child can have 0-n nodes. Each node has a unique identifier (key) Ultimately, the parents are not connected to each other. It seems like this would be a list of trees, however that seems imprecise. I was thinking of joining them with a dummy root.

I need to be able to assembly a list of nodes that occur:

• from any given node down (children)
• from any given node down (children) then up to the root (up to the specific parent)
• the top level parent of any given node (in an O(n) operation)
• the level of the child in the tree (in an O(n) operation)

The structure will contain 300,000 nodes.

I was thinking perhaps I could implement a List of Trees and then also maintain a hash lookup structure that will reference a specific key value to provide me with a node as a starting point.

Is this a logical structure? Is there a better way to handle it? It seems crude to me.

Answer 1

If you are concerned in find a root node quickly you can think of create a tree where each node points to another tree.