From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <Xavier.Leroy@inria.fr>
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 F370E7F8F2
	for <caml-list@sympa.inria.fr>; Mon,  2 Jun 2014 18:57:54 +0200 (CEST)
Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender
  authenticity information available from domain of
  Xavier.Leroy@inria.fr) identity=pra; client-ip=212.27.42.1;
  receiver=mail2-smtp-roc.national.inria.fr;
  envelope-from="Xavier.Leroy@inria.fr";
  x-sender="Xavier.Leroy@inria.fr";
  x-conformance=sidf_compatible
Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender
  authenticity information available from domain of
  Xavier.Leroy@inria.fr) identity=mailfrom;
  client-ip=212.27.42.1;
  receiver=mail2-smtp-roc.national.inria.fr;
  envelope-from="Xavier.Leroy@inria.fr";
  x-sender="Xavier.Leroy@inria.fr";
  x-conformance=sidf_compatible
Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender
  authenticity information available from domain of
  postmaster@smtp1-g21.free.fr) identity=helo;
  client-ip=212.27.42.1;
  receiver=mail2-smtp-roc.national.inria.fr;
  envelope-from="Xavier.Leroy@inria.fr";
  x-sender="postmaster@smtp1-g21.free.fr";
  x-conformance=sidf_compatible
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AoMBAKqsjFPUGyoBnGdsb2JhbABZhx28XoMPAYEVFg4BAQEBAQYNCQkUKIIlAQEEASMPASASEwYLCxgCAgUWCwICCQMCAQIBRRMIAQGINgypNKRfF4EqjS8Wgl+BSwEDmgCGbY96
X-IPAS-Result: AoMBAKqsjFPUGyoBnGdsb2JhbABZhx28XoMPAYEVFg4BAQEBAQYNCQkUKIIlAQEEASMPASASEwYLCxgCAgUWCwICCQMCAQIBRRMIAQGINgypNKRfF4EqjS8Wgl+BSwEDmgCGbY96
X-IronPort-AV: E=Sophos;i="4.98,957,1392159600"; 
   d="scan'208";a="77535106"
Received: from smtp1-g21.free.fr ([212.27.42.1])
  by mail2-smtp-roc.national.inria.fr with ESMTP; 02 Jun 2014 18:57:54 +0200
Received: from [192.168.1.2] (unknown [82.237.71.191])
	by smtp1-g21.free.fr (Postfix) with ESMTP id F0DA49401B1
	for <caml-list@inria.fr>; Mon,  2 Jun 2014 18:55:58 +0200 (CEST)
Message-ID: <538CAD12.2040104@inria.fr>
Date: Mon, 02 Jun 2014 18:57:54 +0200
From: Xavier Leroy <Xavier.Leroy@inria.fr>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.5.0
MIME-Version: 1.0
To: caml-list@inria.fr
References: <543099239773658961@orange.fr> <1401716071976.85ecb8da@Nodemailer>
In-Reply-To: <1401716071976.85ecb8da@Nodemailer>
X-Enigmail-Version: 1.5.2
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
Subject: Re: [Caml-list] Why AVL-tree?

On 02/06/14 15:34, Andrew Herron wrote:
> 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 :)

Yes, we're stupid, of course.

Yoriyuki Yamagata originally asked:

>         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?

At the time Set was written, no efficient algorithms for whole-set
operations (union, intersection, difference, etc) were known for
red-black trees.  I'm not sure they are known today.

As for performance of insert/lookup operations, Jean-Christophe
Filliâtre has measurements showing that OCaml's 2-imbalance AVL trees
perform better than red-black trees.  It all depends on your ratio of
insertions to lookups, of course.  But the 2-imbalance trick makes a
big difference with textbook AVL trees.

- Xavier Leroy