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

[Gabriel Scherer <gabriel.scherer@gmail.com>]

Note that OCaml's balanced trees are not exactly what is usually
called AVL, as the imbalance between different branches can be at most
2 (+1 on one side and -1 on the other) instead of just 1 as the
traditional definition assumes.

On Mon, Jun 2, 2014 at 3:34 PM, Andrew Herron <andrew.herron@gmail.com> wrote:
> Wikipedia has some notes on the difference:
>
> http://en.wikipedia.org/wiki/AVL_tree
>
> AVL has faster lookup, so maybe they decided to optimise for that.
>
> 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 :)
>
>
> On Mon, Jun 2, 2014 at 11:21 PM, Damien Guichard <alphablock@orange.fr>
> wrote:
>>
>>
>> Red-black tree would spare a machine word per node, because a red-black
>> tree doesn't need depth information.
>> Hence the reason is either historical or a space/speed trade-off
>> (comparing two depths may be faster than pattern matching).
>>
>> Regards,
>>
>> damien guichard
>>
>> Hi, list,
>>
>> 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?
>>
>> Best,
>> --
>> Yoriyuki Yamagata
>> http://yoriyuki.info/
>>
>>
>