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 mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by sympa.inria.fr (Postfix) with ESMTPS id 97F177F8F2 for ; Mon, 2 Jun 2014 17:06:46 +0200 (CEST) Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of gabriel.scherer@gmail.com) identity=pra; client-ip=209.85.220.174; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="gabriel.scherer@gmail.com"; x-sender="gabriel.scherer@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail2-smtp-roc.national.inria.fr: domain of gabriel.scherer@gmail.com designates 209.85.220.174 as permitted sender) identity=mailfrom; client-ip=209.85.220.174; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="gabriel.scherer@gmail.com"; x-sender="gabriel.scherer@gmail.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of postmaster@mail-vc0-f174.google.com) identity=helo; client-ip=209.85.220.174; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="gabriel.scherer@gmail.com"; x-sender="postmaster@mail-vc0-f174.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: ArgBAHGSjFPRVdyulGdsb2JhbABZg1lYgmy/agGBCggWDgEBAQEHCwsJEiqCJQEBAQQSER0BGwkUAQMMBgULDQICJgICIQEBEQEFARwGEwgaiAsBAxENpBVqiyeBcoMNmQQKGScNZIUgEQEFDIEeixKCFgeCdYFLBJgIgXiBPot8hAIYKYRqOw X-IPAS-Result: ArgBAHGSjFPRVdyulGdsb2JhbABZg1lYgmy/agGBCggWDgEBAQEHCwsJEiqCJQEBAQQSER0BGwkUAQMMBgULDQICJgICIQEBEQEFARwGEwgaiAsBAxENpBVqiyeBcoMNmQQKGScNZIUgEQEFDIEeixKCFgeCdYFLBJgIgXiBPot8hAIYKYRqOw X-IronPort-AV: E=Sophos;i="4.98,957,1392159600"; d="scan'208";a="77516365" Received: from mail-vc0-f174.google.com ([209.85.220.174]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/RC4-SHA; 02 Jun 2014 17:06:46 +0200 Received: by mail-vc0-f174.google.com with SMTP id ik5so4971714vcb.5 for ; Mon, 02 Jun 2014 08:06:45 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-type; bh=b9+yQVIlOvf/qEUAnKMgb/w6CjZ8eliCM5P9YkRQa6M=; b=N05CgFhTfyBnAojI60RbMFg8134R+h3MTt/j/OUQsV2QK2sI6Jyn8Mt0dMqr5b8xp+ zL+JWfaXAXFbZayD83mxsIHde8lpsbhd/2yu+VM8/I27lDodbuuKb5A2LVHoX1gL8Z3B Pky1ny+F0Vp9os4fhvysiz/9IkqkyVGddRB8PADxppdMCoSbNO+Yb7rESGeQnl3W6j+Z VTGCUNsehqBFkTOYVgKrvIj5YOKT4O7ho2HW+mc9gbqGIndxDUM5n8qjP1f8ebb8y9Ev FS5uua9MrNBr9icbKYcaID2Bi/eURZyAfzsikdaGcBNuX24Xw37vroNu4yhbMF9B7GPe JMLg== X-Received: by 10.58.188.37 with SMTP id fx5mr31243080vec.17.1401721605212; Mon, 02 Jun 2014 08:06:45 -0700 (PDT) MIME-Version: 1.0 Received: by 10.58.90.227 with HTTP; Mon, 2 Jun 2014 08:06:05 -0700 (PDT) In-Reply-To: <1401716071976.85ecb8da@Nodemailer> References: <543099239773658961@orange.fr> <1401716071976.85ecb8da@Nodemailer> From: Gabriel Scherer Date: Mon, 2 Jun 2014 17:06:05 +0200 Message-ID: To: Andrew Herron Cc: Damien Guichard , Caml List Content-Type: text/plain; charset=UTF-8 Subject: Re: [Caml-list] Why AVL-tree? 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 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 > 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/ >> >> >