I am implementing a tree Data structure in c# based (largely on Dan Vanderboom’s Generic implementation). I am now considering approach on handling a Count property which Dan does not implement.
The obvious and easy way would be to use a recursive call which Traverses the tree happily adding up nodes (or iteratively traversing the tree with a Queue and counting nodes if you prefer). It just seems expensive. (I also may want to lazy load some of my nodes down the road).
I could maintain a count at the root node. All children would traverse up to and/or hold a reference to the root, and update a internally settable count property on changes. This would push the iteration problem to when ever I want to break off a branch or clear all children below a given node. Generally less expensive, and puts the heavy lifting what I think will be less frequently called functions.
Seems a little brute force, and that usually means exception cases I haven’t thought of yet, or bugs if you prefer.
Does anyone have an example of an implementation which keeps a count for an Unbalanced and/or non-binary tree structure rather than counting on the fly? Don’t worry about the lazy load, or language. I am sure I can adjust the example to fit my specific needs.
EDIT: I am curious about an example, rather than instructions or discussion. I know this is not technically difficult…
3
You seem to have answered you own question. Have each node hold the count of its descendents plus one (itself). Every time you remove a node you decrement each count on the path back to the root. When inserting you instead increment each count on that path. This way each node contains the total number of nodes in its sub-tree. This will work fine for n-ary trees.
You can even perform the increment/decrement on the way down the tree if you are sure that the node you are inserting/deleting doesn’t/does exist.
EDIT: Removing a node in the middle of the tree. Say you have a tree (labeled with the counts):
|
A(a)
/
B(b) C(c)
Let’s say you delete A and the rules say B should move up to fill it’s place. As we said before you would decrement the counts on the path to the root, but you also need to update B‘s count as it is the new root of the subtree. You have to add C‘s count to B‘s:
|
B(b+c)
/
... C(c)
5
I would suggest to keep a count in the same class that you deifne your Insert and Remove functions.
public class TreeStruct{
private int _count;
private Object rootNode;
public int count{ return count;}
public void Insert(object obj){
//insert object to tree
_count++
}
public void Remove(object obj){
//remove object from tree
_count --;
}
}
6