Re: Queston about Binary Search Trees

[Eric Werk]

Hi Paul,

Binary search trees are not too difficult to write - I gave one I have
implemented in Objective C that I call a PriorityQueue. It does not rely
on the GNU C library (and does not have a "walk" function - yet!) If you
like, I can post the source code - its readable, I think!
At first I wanted it to adopt the KeyedCollection protocol, but it was
such a bother - there were too many non-collection related things to
adopt, so now my PriorityQueue just inherits from SwarmObject.

Here is the header file:

// PriorityQueue.h
#import <objectbase/SwarmObject.h>

@interface PriorityQueue: SwarmObject
{
  int size;
  id subject;
  float priority;
  PriorityQueue *parent;
  PriorityQueue *higher;
  PriorityQueue *lower;
}

- (int) getCount;
- (id) addObject: (id) anObject with: (float) aPriority;
- (id) addQueue: (PriorityQueue *) aQueue;
- (id) getFirst;
- (id) getLast;
- (id) removeFirst;
- (id) removeLast;
@end;

Paul E. Johnson wrote:
> 
> 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.

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