Queston about Binary Search Trees

[Paul E. Johnson]

When I was in Santa Fe last week, I mentioned that a program was running
slowly and Marcus and Vladimir and Alex gave me some ideas, including
the  use of binary search trees.  I expect some of you already have
experience with these things, and if you don't, you might be glad to
know these things exist, so here goes...

In the GNU C library, there is a set of functions--tsearch, tfind, twalk
--that can be used to add nodes (pointers to objects) into a binary
tree, and then searching for elements in that tree is  significantly
faster than searching in a flat list (the difference is n-log(n), where
n is the number of items in the tree (or list)).    

I don't want to bore you with all the details, but I've come to a
somewhat basic question and I think it must be so basic no C book would
ever dignify it with an answer. So here goes. The question is about the
meaning of the term "key" and the usage of the "comparison function".  
Suppose you have a comparison function called "node_compare" and you use
the tsearch function. The tsearch man page says it looks in the tree
and, if that key is not present, it adds it to the tree.  
So, for example, the "key" is the pointer to the object we are looking
for, in this case it is a pointer called "nodeptr", and the name of the
root of the tree is root.  The command looks like:

          (void) tsearch((void *)nodeptr, (void **)&root, node_compare); 

After you finish adding nodes this way, you can write a "print_node"
function that will be executed at each node in the tree by the twalk
command 
        
  twalk(root,print_node);

This tree approach yields exactly the results I'm looking for, except in
one circumstance.  If two objects turn up equal on the "node_compare"
function, the tree will not add the second one. I'm betting that, among
computer people, this is such an obvious property that it goes without
saying.  No?

Why would I want to add objects to a tree when the comparison shows they
are equal? Suppose we are building a tree of people and we use their
height in the comparison function, so we have -1 if  a is shorter than
b, 0 if equal, and 1 a has more height than b.  You can add nodes to the
tree and all is well until you have a second person come along with
exactly the same height as one of the others.  The comparison function
returns 0, that node is not entered into the tree. This is not
satisfactory if one is building the tree to fulfill a later purpose of
finding the 5 tallest people in a group. 

Now, you say, "no duh!" What did I think these BINARY trees were for? 
Binary means two, greater or less than. Well from looking at the man
page, it says the tsearch looks for the key "nodeptr" and, if it is not
present, it adds it to the tree.  Then in the man page there is this
comment under the heading "Return value"
     
 If there are multiple elements that match the key, the element returned
is unspecified.

This makes me think it is possible to insert elements that are indeed
equal. Know what I mean?
How could the man page assume that tree let me insert multiple matching
elements when I can't add elements that are equal?

Assuming I can get this all to work just right, there is a big advantage
out of it. It not only makes the program run more quickly, but it also
lets me cut out about 100 lines of code that were previously dedicated
to sorting items into a list and sifting through it to find the
top-ranked items. Much cleaner and neater!


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