I'm feeling much better than I have been. The mucus factory is pretty much closed. However, I seem to need to drink a heroic amount of water. I constantly feel parched. Must be the wintry weather.
It's still very nasty outside. I'm spending an awful amount of time inside for a Montana boy. Then again, I am getting over an illness and I'm getting pleny of work done.
Speaking of work, I didn't find much to help me with my hash tree problem. I found plenty of stuff about traversal and general graph theory but nothing that specifically helps me.
I think it boils down to doing a traversal. I have to run down the tree until I hit the bottom of a branch, check to see if that child is holding any data, if not delete it. Then go up to the parent of that child, if the parent has no children, then delete it. This goes on until have traversed the whole tree/hash.
Maybe I'll do some more research.
Re:we don't need no stinkin empty nodes
gizmo_mathboy on 2002-03-27T04:26:07
What I'm doing is walking down the tree starting with the parent (it's for a defect tracking system). I see if the parent has any defects. I then go the the children and see if they have any defects and follow down in a depth-first traversal. I can't delete a node unless I know that all the children of it are empty (want to show the relationships).
1
|
---------------
/ | |
2 3 9
/ | \ / \ |
4 5 6 7 8 10
|
11
If only nodes 3,5,and 11 have defects I would want to only display
1
/ | \
2 3 9
| \
5 10
\
11
It's easy to drop nodes at the end, I need to figure out how to know when to prune a parent node. I'm thinking I need to use a flag (positional maybe?)Re:we don't need no stinkin empty nodes
jmm on 2002-03-27T15:13:06
Given a tree that has holes, the simplest method would be a recursive routine. Off the top of my head (i.e. untested and probably containing syntax errors):
$root = prune_tree( $root );
sub prune_tree {
my $node = shift;
my $count = $node->{DEFECT_COUNT};
foreach $child (@{$node->{CHILDREN}}) {
my $subcount = prune_tree( $child );
if( $subcount ) {
$count += $subcount;
} else {
$child = undef;
}
}
return ($count ? $node : undef);
}
You'll have to modify that to whatever is needed for your data structure to get the lvalue list of children and whether there is a defect associated with the node.
However, I still think that the tree should be pruned at the time that the defects are closed. That would be something like:
$root = close_defect( $root, $nodeid, $defectid );
sub close_defect {
my( $node, $nodeid, $defectid ) = @_;
if( $node->{NODEID} eq $nodeid ) {
# find and delete defect $defectid
# (I assume there might be more than one)
...
} else {
my $subnode = # ref to appropriate subnode
$subnode = close_defect( $subnode, $nodeid, $defectid );
}
if( # node has any children or defects ) {
return $node;
}
return undef;
}Re:we don't need no stinkin empty nodes
gizmo_mathboy on 2002-03-27T20:33:55
That is a lot like what I was thinking (although passing pack the count is much cleaner/clearer than setting an explicit flag (and thanks for ignoring my failed attempt at ascii-arting a tree, need pre tags:-)
Thanks for the code and helpng jar loose some ideas.Re:we don't need no stinkin empty nodes
jmm on 2002-03-27T21:21:17
although passing pack the count is much cleaner/clearer than setting an explicit flag
I used the same method in the code for balanced binary trees in the wolf.Re:we don't need no stinkin empty nodes
gizmo_mathboy on 2002-04-10T05:13:48
looks like I need to reread that bit of the wolf...
