Followup about binary trees

[Paul E. Johnson]

A couple of weeks ago I asked in here about binary search trees and got
such great answers I want to ask one more thing. I'm looking for an
explanation of this curious effect. I've found a coding workaround, but
it has left me curious about why things work this way.

This question concerns the tdelete command that is  in the GNU C
library.  My agents assemble these trees with the tsearch command, do
what they need to, and then erase their nodes, collect more nodes and so
forth.  The function "erase_node" is called to do this by the twalk
function.

void
    erase_node (const void *ptr, VISIT order, int level)
    {
      const struct node *p = *(const struct node **) ptr;
      if ((order == endorder) || (order == leaf))
       {
        (void) tdelete(p, &root, node_compare);
         free(p);
        }
     }

twalk (root, erase_node); 

Here is what I find interesting.  Why does a delete function need to
know the compare_function?  The compare_function has one detail in it
that works great when adding nodes but it causes a lot of trouble when
it comes time to delete nodes.  

Let me explain.  The compare function is designed so that it works with
the tsearch function in a particular way.  If the agent finds 2 objects
from the same source, the comparison function returns 0 so the 2nd one
is not added to the tree. If 2 objects are not from the same source,
then the 2nd is added to the tree and a calculation is done to decide
where it should go.   This is junked up with some printfs for debugging: 
int 
node_compare (const void *obj1,const  void *obj2)
{
  int grp1 = [((const struct node *)  obj1) -> recruiter getGrpNumber];
  int grp2 = [((const struct node *)  obj2) -> recruiter getGrpNumber];
 
  double val1 = ((const struct node *)  obj1) -> disutility;
  double val2 = ((const struct node *)  obj2) -> disutility;
  printf("In reportX, grp1=%d, grp2=%d, val1=%f,val2=%f
\n",grp1,grp2,val1,val2);
  if (grp1 == grp2) 
    {
   printf("In reportX, dont understand grp1==grp2\n");
    return 0;
    }
  else if(val1 <= val2) return -1;
  else  return 1;
     
  // return val1 <  val2 ? -1 : val1 != val2;
}

Here is the problem.  The node_compare function checks to see if 2
objects are from the same source (grp stands for "group"). That is
stated as  if (grp1 == grp2) {...}.  In the twalk that calls node_erase,
this condition is true many times, when in fact the tree has no objects
for which grp1==grp2.  I observe that many times the condition holds
because objects are being compared with themselves. Notice in the output
how many grp1 are same as grp2.
In reportX, grp1=0, grp2=0, val1=5.707154,val2=5.707154 
In reportX, dont understand grp1==grp2
In reportX, grp1=1, grp2=1, val1=7.321360,val2=7.321360 
In reportX, dont understand grp1==grp2
In reportX, grp1=1, grp2=1, val1=3.274822,val2=3.274822 
In reportX, dont understand grp1==grp2
In reportX, grp1=1, grp2=1, val1=4.401752,val2=4.401752 
In reportX, dont understand grp1==grp2
In reportX, grp1=0, grp2=0, val1=4.072085,val2=4.072085 
In reportX, dont understand grp1==grp2
In reportX, grp1=3, grp2=3, val1=8.210462,val2=8.210462 
In reportX, grp1=1, grp2=1, val1=6.722131,val2=6.722131 
In reportX, dont understand grp1==grp2
In reportX, grp1=0, grp2=0, val1=5.362310,val2=5.362310 
In reportX, dont understand grp1==grp2
In reportX, grp1=2, grp2=2, val1=4.195993,val2=4.195993 
In reportX, dont understand grp1==grp2
In reportX, grp1=3, grp2=3, val1=6.359044,val2=6.359044 
In reportX, dont understand grp1==grp2
In reportX, grp1=2, grp2=2, val1=8.981669,val2=8.981669 
In reportX, dont understand grp1==grp2

I got curious about this and tracked it down because I want to put a
command or two in the if (grp1==grp2) statement, and if the
compare_nodes function is called only in the tree-building stage, all is
well and those added commands do what I want (execute only when objects
from the same source are found).  But adding that code causes a mess
when the delete phase starts.  I can work around this by tailoring 2
very similar compare functions, so I'm not asking for coding help. 

But what I do need is an explanation for this curious behavior of the
twalk that deletes nodes.  

See, there is something about binary trees that I still don't get.

-- 
Paul E. Johnson                         email: address@hidden
Dept. of Political Science              http://lark.cc.ukans.edu/~pauljohn
University of Kansas                    Office: (785) 864-9086
Lawrence, Kansas 66045                  FAX: (785) 864-5700

                  ==================================
   Swarm-Support is for discussion of the technical details of the day
   to day usage of Swarm.  For list administration needs (esp.
   [un]subscribing), please send a message to <address@hidden>
   with "help" in the body of the message.