Re: [Caml-list] Why AVL-tree?

[Xavier Leroy <Xavier.Leroy@inria.fr>]

On 02/06/14 15:34, Andrew Herron wrote:
> It's different to some other languages I've seen, but then so is their
> decision to not use a tail recursive List.map. Each to their own, it's not
> hard to implement the alternative :)

Yes, we're stupid, of course.

Yoriyuki Yamagata originally asked:

>         Just from the curiosity, why balanced binary trees used in Set and
>         Map are AVL-trees, not their alternative, say, red-black trees?  Is
>         there a deep reason for it, or just a historical one?

At the time Set was written, no efficient algorithms for whole-set
operations (union, intersection, difference, etc) were known for
red-black trees.  I'm not sure they are known today.

As for performance of insert/lookup operations, Jean-Christophe
Filliâtre has measurements showing that OCaml's 2-imbalance AVL trees
perform better than red-black trees.  It all depends on your ratio of
insertions to lookups, of course.  But the 2-imbalance trick makes a
big difference with textbook AVL trees.

- Xavier Leroy