# Insert function for general trees

This topic is 3057 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 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 on other sites
For the insert part of the tree, do we let the user get the children of the parent
and then let them insert it, or do we handle it internally somehow?

##### Share on other sites
It's your class. How do you want to use it?

##### 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 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 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 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 theproper 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 newnode?
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.

Thanks Antheus.

1. 1
Rutin
25
2. 2
3. 3
4. 4
JoeJ
18
5. 5

• 14
• 14
• 11
• 11
• 9
• ### Forum Statistics

• Total Topics
631757
• Total Posts
3002141
×