From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@sympa.inria.fr Delivered-To: caml-list@sympa.inria.fr Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by sympa.inria.fr (Postfix) with ESMTPS id 77F227F8F2 for ; Mon, 2 Jun 2014 15:34:34 +0200 (CEST) Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of andrew.herron@gmail.com) identity=pra; client-ip=209.85.216.44; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="andrew.herron@gmail.com"; x-sender="andrew.herron@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail3-smtp-sop.national.inria.fr: domain of andrew.herron@gmail.com designates 209.85.216.44 as permitted sender) identity=mailfrom; client-ip=209.85.216.44; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="andrew.herron@gmail.com"; x-sender="andrew.herron@gmail.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of postmaster@mail-qa0-f44.google.com) identity=helo; client-ip=209.85.216.44; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="andrew.herron@gmail.com"; x-sender="postmaster@mail-qa0-f44.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AsIBAJ98jFPRVdgslWdsb2JhbABZgkKBF4NEqgOEDIhfgUIBhzgBgREWDgEBAQEHDQkJEiqCJQEBAQMBDwECER0BGwIHCQsBAwwGBQQKEwQdAgIPFBEBBQEKEgYTEhCICwEDCQgDAgijdmqKLwEBdoFygw2YcgoZJwMKZIUgEQEFDI5GB4I0DzISgTkEhF8FhUGGEIsJj35BhQg X-IPAS-Result: AsIBAJ98jFPRVdgslWdsb2JhbABZgkKBF4NEqgOEDIhfgUIBhzgBgREWDgEBAQEHDQkJEiqCJQEBAQMBDwECER0BGwIHCQsBAwwGBQQKEwQdAgIPFBEBBQEKEgYTEhCICwEDCQgDAgijdmqKLwEBdoFygw2YcgoZJwMKZIUgEQEFDI5GB4I0DzISgTkEhF8FhUGGEIsJj35BhQg X-IronPort-AV: E=Sophos;i="4.98,957,1392159600"; d="scan'208";a="65032898" Received: from mail-qa0-f44.google.com ([209.85.216.44]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 02 Jun 2014 15:34:33 +0200 Received: by mail-qa0-f44.google.com with SMTP id j7so2674494qaq.31 for ; Mon, 02 Jun 2014 06:34:32 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=date:mime-version:message-id:in-reply-to:references:from:to:cc :subject:content-type; bh=prPtwKIW5HslEnTV+smNhm9gXCztKA4l+EA5cj0uH68=; b=Sf5msJ07NX7UZCFgyEvdCoqu0jBPwfr0DXLJXL6YPBpqL5ilM+MVYU+TKg9i65GOH1 uWgwT6aw0pcHXE8kBCuG+rqdwm0/eSeFCS7jsJ6wfCZtZgSqrJ9PA1n1aqlMd4vaBr4Z iOkjsb4tJmMLwsCok6jR/OsSK0L9BrN3gL0AySCEhh0yS0VA0UIhPtCN6YvR0ppzQLWj L6iSHa0Xz5uUuV663kJps69e0Vpbej6M1eZh2FiJqD6pb4Xyg83FgC5RnqtU7nr8LbE/ bsszsLtd6E+NaPSXKXwsesGM9Ka4jxMXHrd3ycBOoP+UwMLIvcdjhCm0PpYaKb/BsyQ0 ZNkQ== X-Received: by 10.224.80.138 with SMTP id t10mr51360452qak.0.1401716072635; Mon, 02 Jun 2014 06:34:32 -0700 (PDT) Received: from hedwig-53.prd.orcali.com (ec2-54-85-253-117.compute-1.amazonaws.com. [54.85.253.117]) by mx.google.com with ESMTPSA id e12sm21488533qaq.13.2014.06.02.06.34.32 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Mon, 02 Jun 2014 06:34:32 -0700 (PDT) Date: Mon, 02 Jun 2014 06:34:32 -0700 (PDT) X-Google-Original-Date: Mon, 02 Jun 2014 13:34:31 GMT MIME-Version: 1.0 X-Mailer: Nodemailer (0.5.0; +http://www.nodemailer.com/) Message-Id: <1401716071976.85ecb8da@Nodemailer> In-Reply-To: <543099239773658961@orange.fr> References: <543099239773658961@orange.fr> X-Orchestra-Oid: D774D412-32ED-437C-B75B-60B7D2EC9751 X-Orchestra-Sig: e4c44aa0fd30f0c25e847559c4d15b6a97ad2543 X-Orchestra-Thrid: TFCB197D0-2259-48F9-945B-A13194F980E2_1469799221824128502 X-Orchestra-Thrid-Sig: 07148fda78d20acf5beffc903de45f29685e5c34 X-Orchestra-Account: b0b4c43c46e5ef3758d4d74db62406ec12d5e276 From: "Andrew Herron" To: "Damien Guichard" Cc: "Caml List" Content-Type: multipart/alternative; boundary="----Nodemailer-0.5.0-?=_1-1401716072207" X-Validation-by: andrew.herron@gmail.com Subject: Re: [Caml-list] Why AVL-tree? ------Nodemailer-0.5.0-?=_1-1401716072207 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable 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 deci= sion 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 wrote: >=20=20 > Red-black tree would spare a machine word per node, because a red-black t= ree > doesn't need depth information.=20 > Hence the reason is either historical or a space/speed trade-off (compari= ng > two depths may be faster than pattern matching).=20 >=20=20 > Regards, >=20=20 > damien guichard=20 > Hi, list,=20 > 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, > --=20 > Yoriyuki Yamagata > http://yoriyuki.info/ > --=20 > 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= ------Nodemailer-0.5.0-?=_1-1401716072207 Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: quoted-printable Wikipedia has some notes on the differenc= e:

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 <alphablo= ck@orange.fr> wrote:

=C2=A0
Red-black tree would=C2=A0spare a machine word per node, because=C2= =A0a red-black tree doesn't need depth=C2=A0information.=C2=A0
Hence=C2=A0the reason is either historical or a space/speed trade-o= ff (comparing two depths may be faster than pattern matching).=C2=A0=
=C2=A0
Regards,
=C2=A0
d= amien guichard=C2=A0
Hi, list,=20

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

Best,
--
Yoriyuki Yamagata
http://yoriyuki.info/


= ------Nodemailer-0.5.0-?=_1-1401716072207--