Sign in to follow this  
Concentrate

Insert function for general trees

Recommended Posts

This question is about general tree, specifically the insert function. Since in theory a root can have many child, there could possibly be infinite children for a root. Therefore do we usually set a limit on the number of child a parent node can have? Also in general trees, we COMPARE the element with the proper node and insert it in the proper place? Is it always like this, I mean in general trees, do we always use some sort of comparison, to insert a new node? Thanks.

Share this post


Link to post
Share on other sites
A fully general tree has no limitations on the number of children a node can have or the relationship the contents of each node with each other. As soon as you specifying either of those you no longer have a general tree; you have a specific tree of some type or another.

Share this post


Link to post
Share on other sites
I am really not sure. I was thinking there was some general ways one does it
usually. I guess it would be easier me if I let the user add the childs, but
then that gives them a chance to disrupt the structure of the tree. So I am not
sure. How hard would it be to implement a general insert function for the tree?
I am trying to think about it, but am open to suggestions.

Share this post


Link to post
Share on other sites
You are trying to over generalise this, I suspect. Write something simple that works now, if it needs to become more general later you can refactor later.

I would be inclined to try an encapsulate as much as possible, so you can maintain any invariant you want over the ordering.

Share this post


Link to post
Share on other sites
So far this is how the interface works, what do you guys think? Its a bit
simplistic, but I wanted to get it to work for now :

public static void main(String[] arg){
Tree<String> tree = new GeneralTree<String>("L");
tree.addChild("E");
tree.addChild("N");

TreeChild<String> child = tree.getChildren();
if(child.hasAnotherChild()){
child.add("B"); //add child to "E"
child.add("H"); //add child to "E"
}
child.moveNext(); //move to next child
if(child.hasAnotherChild()){
child.add("R"); //add child to "N"
//get children of "R" node
TreeChild<String> subChild = child.getChildren();
subChild.add("P");
}
child.moveNext();

if(child.hasAnotherChild()){//does not execute
child.add("False");
}

tree.printPostOrder(); //prints B,H,E,P,R,N,L
print();
tree.printPreOrder(); //prints L,E,B,H,N,R,P
print();
}

Share this post


Link to post
Share on other sites
A general Tree ADT has arbitrary order, and insertions may change it. Horrors like splay or AVL trees come to mind.

So the textbook definition is:
Insert(T, v) // Insert v into tree t

The OO version would be:
Tree::Add(v);


The OO design of being able to operate on child nodes directly may be tempting, but doesn't work all that well in practice, especially not for general tree structure.

Quote:
Also in general trees, we COMPARE the element with the
proper node and insert it in the proper place?

In general tree you cannot make any assumptions. Only the tree implementation knows how, why and where to put the node, and how to rearrange the rest of the tree.

Quote:
I mean in general trees, do we always use some sort of comparison, to insert a new
node?
No. Some trees do maintain strict ordering, others could try to balance the number of children regardless of order. A tree is just a special case of a graph with no guarantees on order of elements.


For traversal it is also common to define the following:
- GetFirstChild(T, v); // first child of v
- GetNextSibling(T, v); // next sibling (same level) of v

Since this would require too much traversal, the GetFirstChild would typically be implemented as returning an iterator object.


I suppose that designing a general tree class simply isn't practical, each type has its own pecularities and often the performance impact (the O(n)) of general solution isn't viable.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this