Re: avl-trees vs. hashes

[Jay Glascoe <jglascoe@jay.giss.nasa.gov>]

On 23 Oct 1998, Sascha Ziemann wrote:

> Jay Glascoe <jglascoe@jay.giss.nasa.gov> writes:
> 
> | Just a thought: how about a hash table with avl-trees for buckets?
> 
> Trees are only worth to be used, when used with a big number of
> elements, because of the O(log(n)).  The bigger the number the better
> they are.

yeah, I've thought about it, using avl-trees for buckets is rather
pointless.  But how about using hash tables for the sub-trees of an
avl-tree?  Hmmmm?  (I include a winking smiley for the humor-impaired ;) 

you know, I've been so intrigued by these avl-tree things, I've been
planning for a while now to do a C extension of them for Guile.  From what
I understand, the basic representation of an avl-tree isn't all that
complicated, just binary trees with some extra book-keeping.  The hard
part, of course, is the implementation of the insertion and removal
procedures.  (These routines for avl-trees make hash tables look like
childs' play ;)

Once I get my hash tables in order, I plan on proto-typing the
implementation and then porting that to a Guile C extension.

> -- 
> /* In the beginning was the Word: */
> typedef long SCM;
> 
amen