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 1BBC67F8F2 for ; Mon, 2 Jun 2014 15:21:09 +0200 (CEST) Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of alphablock@orange.fr) identity=pra; client-ip=80.12.242.123; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="alphablock@orange.fr"; x-sender="alphablock@orange.fr"; x-conformance=sidf_compatible Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of alphablock@orange.fr) identity=mailfrom; client-ip=80.12.242.123; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="alphablock@orange.fr"; x-sender="alphablock@orange.fr"; x-conformance=sidf_compatible Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of postmaster@smtp.smtpout.orange.fr) identity=helo; client-ip=80.12.242.123; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="alphablock@orange.fr"; x-sender="postmaster@smtp.smtpout.orange.fr"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AosDABh5jFNQDPJ7lWdsb2JhbABZgkKBF4NEgXClVgaPIIoiDgEBAQEHDQkJEiqCT0IvBAEVAiYCX4hAARihBo8inW4BhnKBKoQri3mBSwSQNYlLgT53hDiPeg X-IPAS-Result: AosDABh5jFNQDPJ7lWdsb2JhbABZgkKBF4NEgXClVgaPIIoiDgEBAQEHDQkJEiqCT0IvBAEVAiYCX4hAARihBo8inW4BhnKBKoQri3mBSwSQNYlLgT53hDiPeg X-IronPort-AV: E=Sophos;i="4.98,957,1392159600"; d="scan'208,217";a="65030897" Received: from smtp01.smtpout.orange.fr (HELO smtp.smtpout.orange.fr) ([80.12.242.123]) by mail3-smtp-sop.national.inria.fr with ESMTP; 02 Jun 2014 15:21:08 +0200 Received: from [192.168.1.10] ([90.29.164.130]) by mwinf5d24 with ME id 9RM71o00m2p7BXe03RM8Uv; Mon, 02 Jun 2014 15:21:08 +0200 X-ME-Helo: [192.168.1.10] X-ME-Auth: YWxwaGFibG9ja0B3YW5hZG9vLmZy X-ME-Date: Mon, 02 Jun 2014 15:21:08 +0200 X-ME-IP: 90.29.164.130 From: "Damien Guichard" To: "Caml List" Content-Type: multipart/alternative; charset="UTF-8"; boundary="TdxxJf=_O8dNncJgDtn8r62CaUh1ngKHww" MIME-Version: 1.0 Date: Mon, 2 Jun 2014 15:21:02 +0200 Message-ID: <543099239773658961@orange.fr> X-Mailer: EssentialPIM Portable v. 4.54 X-Validation-by: alphablock@orange.fr Subject: Re: [Caml-list] Why AVL-tree? This is a multi-part message in MIME format --TdxxJf=_O8dNncJgDtn8r62CaUh1ngKHww Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable =20 Red-black tree would spare a machine word per node, because a red-black tree doesn't need depth information.=20 Hence the reason is either historical or a space/speed trade-off (comparing two depths may be faster than pattern matching).=20 =20 Regards, =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/ --TdxxJf=_O8dNncJgDtn8r62CaUh1ngKHww Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
 
Red-black tree would spare a machine word per node, because&nb= sp;a red-black tree doesn't need depth information. 
Hence the reason is either historical or a space/speed trade-o= ff (comparing two depths may be faster than pattern matching). =
 
Regards,
 
damien guichard =
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,
--
Yoriyuki Yamagata
http://yoriyuki.info/

--TdxxJf=_O8dNncJgDtn8r62CaUh1ngKHww--