0

Name of data structure that's tree-like with multiple root nodes

I stumbled upon someone's answer to a question regarding implementing a tree that has > 2 nodes above. I just wanted to get someone's thoughts on using a Forest Data Structure to implement a Family Genealogy Tree that consist of multiple nodes with 0-multiple children. I may use a Forest Tree, however from most representations that I searched up on and found, it looks similar to a disjointed set, but I do not want a parent node to already be pre-destined to have no children. I hope it makes sense what I am saying. Any advice or comments you could offer would be much appreciated.

  • A forest is nothing more than a bunch of individual trees (as indeed is a disjointed set). I am not sure what your problem is, or what you expect a special forest data structure to be able to do. There is nothing pre-destined or fixed about a forest either. Each tree can be modified just like a normal tree data structure. Maybe you could elaborate a bit more or add examples of what sort of questions you want the data structure to be able to answer? – Frank Sep 14 '15 at 6:08
  • So consider using a simple ArrayList in each node to represent the children. To save up space, you should probably initialize them with a small amount of initial capacity (even 0). I fail to see the issue. If you want to be able to start at any node and expand (family members of John Smith), then maybe a more arbitrary graph model would be better suited. – Neil Sep 14 '15 at 6:22
  • Thanks for your input guys! I wanted to produce a tree of some sort of data-structure entity that would contain information about a node and possess more than 2 children nodes, unlike the BInary Tree structure. I would want to be able to access a child node via its parent and vice-versa through which a tree gui would be represented showing birth/marriage/death records of each individual person. A person obviously being represented by a single node who may have 0->2 siblings. Perhaps further implementing siblings from one parent. I would like to use a data structure other than an ArrayList, – Tj895 Sep 14 '15 at 6:33
2

I hope I have a clear enough understanding of what your problem is. If I'm off-track let me know, otherwise the following should be of some help to you.

Just to be clear: I will consider all of the below under the context of genealogy.

A tree is simply a branching structure. In genealogy, you could consider the latest child as the root and create a tree that describes the ancestry of this person. Yes, the latest child is the root, not the oldest known ancestor. This is quite counter-intuitive and probably not really what you want anyways.

Now, once you have more complicated family issues, like a man having children with two different women, you'll run into problems with trees. If you have a separate tree for each child, then the father needs to be duplicated to be able to occur in each of these trees. Unpractical to say the least.

As Neil mentioned in his comment above, it is time to switch to a graph model. Most important for this is to clear up a typical confusion: The general populace speaks of something called a "Family genealogy tree", but as a computer scientist you must realize that such a tree is no tree as per the definitions given in computer science (or biology for that matter). We have a very clear and concise mathematical definition of a tree data structure, and a "genealogy tree" does not match it.

Why is that? Simply because in computer science trees, the different branches are not able to grow back together. With families, this is possible. Quite drastically, you could have the case of a father with two childrens, which again spawn an off-spring. Moral implications aside, this results in a diamond-like view, which is not representable in a tree.

Enter the world of graphs: A graph is just a generic term of things that are connected to each other. Hence, every computer science tree is also a graph. A very special and restricted one of course. In a graph, there is no root anymore, but there are nodes with similar properties (called sources). There are also no leaves anymore, but again nodes with similar properties (called sinks).

In terms of genealogy you can limit the result graph by making it a DAG, a directed acyclic graph. It is directed, because between two nodes, you can declare one as the parent side, one as the child side. For example, you could always point from parent to child (that's one direction, the other is feasible too). If you want to be able to traverse this structure in both directions, you may even consider an undirected variant.

Acyclicity simply means, that there are no circles in your data structure. It is pretty clear that this applies to genealogy (unless you want to count in time traveling and the implied option of becoming your own father or mother). In a DAG, you can have any number of nodes and connections between them. You can however add arbitrary limitations. For example, if all connections go from parent to child, then each child node could be restricted to have a maximum fan-in of 2. That's just graph theory lingo for saying that a person cannot have more than two parents.

Hence, I suggest to take a close look at directed acyclic graphs and the underlying graph theory in general. Also note that it'll pay off. If you want to do software development you should know about graphs. They are one of the most general data structures and apply to almost everything. They are not always the best choice of course, but they will be one of the most powerful things in your arsenal.

  • Thank you Frank for the suggestion. I will look further into graphs as you advised, hypothetically say if I were to use a graph or in this instance a DAG would I be able to allow a child node to share the same parent as another child, therefore implementing half siblings? – Tj895 Sep 14 '15 at 7:05
  • Also, Djikstra's Algorithm and Bell-man Ford would be a practical example of a DAG if I am not mistaken? Please feel free to correct me. – Tj895 Sep 14 '15 at 7:11
  • Yes, sharing the same parent is no problem in a DAG, since it is just another connection between the corresponding nodes. Dijkstra's and Bellman Ford are algorithms as opposed to data structures. They are possible ways to work with a graph once you have one. – Frank Sep 14 '15 at 7:27
  • Would this be the best way of commencing implementation for a DAG? stackoverflow.com/questions/15460661/… – Tj895 Sep 14 '15 at 11:47
  • There is no generic "best" in software engineering. You can hand-code it, you can choose one of the 2355113 (rough estimate) graph libraries.. a lot more info is needed for this decision and it's probably not one that SE can help you with. – Frank Sep 14 '15 at 12:21
0

These posts are old, but here is my input anyway.
First of, I think the solution is much simpler than using graphs.
I would implement a class, let us call it Node, which has person name and other attributes that you may like to keep for each person in the family. Then we need another attribute to add it to class Node, which is an array of (references) of the same type (Node). These are the children of a particular parent. At first they all will be set to null, then you can instantiate any number of children based on what you have and link them to this particular parent. For example, the class may start like this:

class Node
{
    private string name;  // person name
    private int data; // any data about the person i.e number of teeth :)
    private Node [] children;  // reference to array of children
    public void Node() // constructor
    {
        // here put code to instantiate the array, for example
    }
    // other methods, for example setters and getters
}

This way the oldest known grandfather will be in the root Node. each Node has number of children based on the real case, which are references to objects of the same type etc... You will probably need to write some methods for traversing the forest, in order to be able to print it, or search for particular person, etc. You may look at data structures books in java or C# to learn more about implementing linked-based trees in general. I hope this is useful for any one need to implement a forest using object-oriented paradigm.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.