Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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...

share|improve this question
1  
Is there a reason you can't keep a count of all nodes which would get updated with every insert/remove? –  DFord Oct 12 '12 at 14:15
    
That is the example I am thinking about. Imagine a tree 20 levels deep. I add a node to the 20th level. Do I walk the tree and keep a count at the root node? What if I remove a branch at level 10? There are several cases to consider. It must be more complicated then it seems or I would be able to easily find samples. So, I am looking for a sample –  Spevy Oct 12 '12 at 14:20
1  
@Spevy: I think the reason you're not finding any examples is that it really is as easy as it seems. This is one of those "actual code left as an exercise for the reader" type of problems. –  TMN Oct 12 '12 at 16:40
add comment

2 Answers

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)
share|improve this answer
    
As noted above. Seems straight forward, but surely I am not the first with this problem, but I can't find a sample implementation which makes me think I am over looking something. –  Spevy Oct 12 '12 at 14:24
2  
@Spevy I think you're overestimating how commonly people working in C# are writing trees, the reason you don't find other people doing this is because the majority of software written in C# is much more straight forward to the point that data structures don't really become a topic. Data structures matter for the hardcore data processing C# applications out there of which there are considerably less than you'd expect, people are still sticking with C++ or java for those things out of tradition –  Jimmy Hoffa Oct 12 '12 at 14:34
    
Happy to have a C++ or java example. I am not picky! –  Spevy Oct 12 '12 at 14:36
    
@Spevy Also to add to Jimmy Hoffa, knowing the size of each sub-tree is not generally a useful number as most trees are used for searching. In a search tree (especially an unbalanced one) the sub-tree count would depend on the order of insertion. –  axblount Oct 12 '12 at 14:39
    
@axblount, if I was doing a searchable tree, I would likely go with a Hash or binary tree structure. In this case I am dealing more a graph type problem where relationships between nodes can change but will follow the rules of a tree. –  Spevy Oct 12 '12 at 14:59
add comment

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 --;
    }
}
share|improve this answer
    
Thanks @DFord since this is an unstructured Tree, and not a Binary tree, the addition of Nodes could be anywhere in the tree. Think of a W3C node as an example which can add children to itself. –  Spevy Oct 12 '12 at 15:20
    
@spevy so each Node will have an insert function and when a new node is inserted, will you traverse to the insert location by starting at the root node? –  DFord Oct 12 '12 at 15:25
    
Each node can only add a child to itself so there is no traversal required (at less just to add the node to the tree). The specifics of adding and removing and incrementing a counter to a shared pointer/reference is not what I am worried about. I am more interested in the complexities introduced by moving, copying, deleting, branching to new trees or clearing nodes. –  Spevy Oct 12 '12 at 15:32
    
Where do you keep track of all the references to each node? From there you should be able to get a count. –  DFord Oct 12 '12 at 16:33
    
It's a tree so each node is only aware of its parent and children. –  Spevy Oct 12 '12 at 16:38
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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