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





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