5

I'm attempting to implement a data structure, and using a more traditional tree data structure, but I'm not using the root node as it holds no real value in the context I'm using it in.

Ideally, I want to use a structure that is a tree, but that has multiple root nodes (and that is not just a list of trees). Is there a name for a data structure like this?

Seer
  • 155
  • 1
  • 6
  • Oh yeah? It is not just a list of trees? Why so? – Mike Nakis May 31 '15 at 16:15
  • Hell, maybe it is and I'm simply over-thinking it. – Seer May 31 '15 at 16:16
  • 4
    A set of unconnected trees would be called a [forest](https://en.wikipedia.org/wiki/Tree_%28graph_theory%29#forest). A list of trees can be a valid implementation of a forest, assuming that no two trees in the list have any node in common. – amon May 31 '15 at 16:22
  • 1
    If the trees are connected you call it a [multitree](https://en.wikipedia.org/wiki/Multitree). – User May 31 '15 at 20:40

2 Answers2

7

You don't have one tree with multiple roots, you have a grab bag of separate trees, each with a unique root. In graph theory, a bunch of disconnected trees are called forest. But if the trees don't really belong together, it might be more useful to think of it just as a collection (list, map, etc.) of trees.

  • A forest... I like that. They are all related, they hold the same type of information, in the same structure. They're basically paths, and some of the paths may have different starting points. – Seer May 31 '15 at 16:22
1

Try for Forest Data structure using Java Programming. I have done this already and it's easy. As Java API contains no general API for trees/graphs, since there is no unique set of features needed in every use case. There are quite some tree/graph-like APIs for special cases, though.And it is easy to make your own graph - one could even say that every object is in fact a node in a graph, with the values of its reference type fields being the (outgoing) neighbors. I had even implemented search using hashing techniques to find the immediate parent and immediate child node, if exists.

BaBa Somanath
  • 11
  • 4