About AVLtrees (was Re: Query: Spatially uncorrelated reproducible random values

[Paul E Johnson]

"Marcus G. Daniels" wrote:
> 
> Otherwise, I'd use a hash table or maybe the AVL implementation in misc/.
> 
I just wanted to mention that I've done some experimenting with the
AVLtree and I've put two example programs in
http://lark.cc.ukans.edu/~pauljohn/SwarmFaq/WorkingExampleCode/objc

the first one, avlusage.m, shows the creation of an avl_tree and
insertion and recall of objects in it.  avlusage2.m is the beginnings of
a separate class AVLSet, which could replace the Swarm Set class if I
filled in a few methods.  AVLSet is basically an Objective-C wrapper
around the C code from the avl_tree. I  plan to work on an AVLMap class
as well, and when I have something to show it will popup in there.

The "sales pitch" for the avl tree is the ability to locate specific
items more quickly than the linked lists used in the current Swarm
library.  Whereas a Swarm list has to check items one-by-one until it
finds the one that you want, an avl tree has structure that speeds up
the search a lot.  trees also have a "walk" function that can apply a
given action to each element in the tree (saving you the trouble of
writing a loop!).  

I didn't realize avl_tree was in the swarm source until lately, and
before that I had used the "bsearch" (binary search tree) in glibc for a
job here and there. Something funny happened in one edition of glibc and
it was not deleting objects the way I expected, and so I gave up on the
bsearch tree.  I find the interface to the avl_tree to be much more to
my liking. 

If you dig into avl, you need to go here:
http://www.msu.edu/user/pfaffben/avl/

Swarm currently includes only the avl portion of the library, not the
avlt or avltr versions.
  
-- 
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-Modelling is for discussion of Simulation and Modelling techniques
   esp. using Swarm.  For list administration needs (esp. [un]subscribing),
   please send a message to <address@hidden> with "help" in the
   body of the message.
                  ==================================