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] |
> 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