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

> 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? :)

Nope;  deletion is O(1) is a properly-implemented hashtable.

One advantage of AVL (and other balanced) trees is
they allow convenient sequential access.  You could add that on
top of hashing.  However, what you can't do using hashing is
range queries, such as "find the first key greater than
a given value".  Hash tables take O(n) for those, while
AVL trees O(log n).

	--Per Bothner
Cygnus Solutions     bothner@cygnus.com     http://www.cygnus.com/~bothner