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

Chris.Bitmead@misys.com.au writes:

 > >So when worrying about the worst case, doing lots of insertions,
 > >deletions, ordering and the like, balanced trees are better, although
 > >they are not implemented by the guile-core?
 > 
 >    Worst case for balanced trees is an in-order insertion. That makes
 >    lots of rebalancing of the tree. Unfortunately, in-order insertion
 >    is a common case.
 > 
 >    On the other hand, provided a hash table has a truely random hash,
 >    the worst case is so unlikely to happen it's not worth thinking
 >    about.

Worst case is still O(log(n)) for each insertion.

-- 
Harvey J. Stein
BFM Financial Research
hjstein@bfr.co.il