Re: avl-trees vs. hashes

[Maciej Stachowiak <mstachow@mit.edu>]

jglascoe@jay.giss.nasa.gov writes:
> On Mon, 19 Oct 1998, Klaus Schilling wrote:
> 
> > 
> > What are the most striking advantages of hashes over avl-trees (or other
> > tree-based search structures) that pushed the guile developers into supp
> orting
> > only hashtables directly? Are binary-tree structures particularly bad fo
> r
> > Scheme?
> > 
> 
> Unless I'm mistaken, avl-trees do insertion and retrieval in O(log n)
> time.  Whereas hashes can do both in O(1), constant, time.  But it's
> possible avl-trees are faster at deletion? anyone... anyone? :)

Yes, AVL trees are logarithmic. Their advantages include not needing a
hash function, being able to easily traverse pre-order, in-order or
post-order and various other nice properties.

Actually red-black trees are simpler to implement than AVL trees and
are just as good.

> I'm working on deletion and downsizing for my hashtables right now.
> Deletion seems to be REAL SLOW, because I basically have to rebuild a
> bucket (basically an alist) every time I remove an entry.  I could use
> "dummy entries" or something, but that seems like such an ugly solution.

Do you really need to rebuild the whole bucket? Can't you delete the
offending element destructively? i.e. set-cdr! the preceding cell to
the cdr of the cell that has the pair you want to remove.

 - Maciej