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

["Andrew Herron" <andrew.herron@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 1244 bytes --]

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/
> -- 
> Caml-list mailing list.  Subscription management and archives:
> https://sympa.inria.fr/sympa/arc/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs

[-- Attachment #2: Type: text/html, Size: 2110 bytes --]