This is the mail archive of the guile@cygnus.com mailing list for the guile project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

Re: avl-trees vs. hashes

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 supporting
> only hashtables directly? Are binary-tree structures particularly bad for
> 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? :)

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.

	Jay
	jglascoe@jay.giss.nasa.gov