From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <yoriyuki.y@gmail.com>
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 2C9A67F8F2
	for <caml-list@sympa.inria.fr>; Mon,  2 Jun 2014 13:49:11 +0200 (CEST)
Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender
  authenticity information available from domain of
  yoriyuki.y@gmail.com) identity=pra; client-ip=209.85.216.45;
  receiver=mail2-smtp-roc.national.inria.fr;
  envelope-from="yoriyuki.y@gmail.com";
  x-sender="yoriyuki.y@gmail.com";
  x-conformance=sidf_compatible
Received-SPF: Pass (mail2-smtp-roc.national.inria.fr: domain of
  yoriyuki.y@gmail.com designates 209.85.216.45 as permitted
  sender) identity=mailfrom; client-ip=209.85.216.45;
  receiver=mail2-smtp-roc.national.inria.fr;
  envelope-from="yoriyuki.y@gmail.com";
  x-sender="yoriyuki.y@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-qa0-f45.google.com) identity=helo;
  client-ip=209.85.216.45;
  receiver=mail2-smtp-roc.national.inria.fr;
  envelope-from="yoriyuki.y@gmail.com";
  x-sender="postmaster@mail-qa0-f45.google.com";
  x-conformance=sidf_compatible
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: ArMBAFZjjFPRVdgtm2dsb2JhbABYg1lYgmy2bIoDCBYOAQEBAQEGCwsJFCiCHCIRHQEbCRUDEggBAgU3AiQBEQEFASI1iAsBAxGgW4MRaosngXKDDZhkChknDWSFIBEBBQyRQoFLBIojj12BPo9+GCmEdy4
X-IPAS-Result: ArMBAFZjjFPRVdgtm2dsb2JhbABYg1lYgmy2bIoDCBYOAQEBAQEGCwsJFCiCHCIRHQEbCRUDEggBAgU3AiQBEQEFASI1iAsBAxGgW4MRaosngXKDDZhkChknDWSFIBEBBQyRQoFLBIojj12BPo9+GCmEdy4
X-IronPort-AV: E=Sophos;i="4.98,956,1392159600"; 
   d="scan'208";a="77476265"
Received: from mail-qa0-f45.google.com ([209.85.216.45])
  by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/RC4-SHA; 02 Jun 2014 13:49:10 +0200
Received: by mail-qa0-f45.google.com with SMTP id hw13so2436349qab.4
        for <caml-list@inria.fr>; Mon, 02 Jun 2014 04:49:09 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=gmail.com; s=20120113;
        h=mime-version:from:date:message-id:subject:to:content-type;
        bh=S3wt9okNu+NfTSXWixgGRgOBSs+7IXuet83q0SjDPLo=;
        b=EmHPKaWhaK4Lj+MxpsTRsTToEmVkJNcJQC967W1WtBAHTxqZK62brHKo5Vf9KvniMq
         y7cr4SV//kneaN60akri9HaZHRLb6p61+X/ACo0d2wZIy5SO1ZjXXu+3gv4d2alx9I5R
         pL0cOWnv25bpK7RmloCrHXeiFTXlvxUjUxKSmhE3VfKj9AEWoiR/1JMySGUhy/DR/3US
         pgWxMzFmq8RMGzpmeKJvs0NLWkpFrXJtiea1ReX6tjiDuu5TWZQ5bgJ7XgYyY43ODH3N
         W9kSsnk65g4L5OuYN22Rwel8pPoLgrJTbUVMExibpUEZFYkT8KlqLQYRXjq/03kmBjYG
         NOfw==
X-Received: by 10.224.67.201 with SMTP id s9mr48256881qai.29.1401709749575;
 Mon, 02 Jun 2014 04:49:09 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.140.41.228 with HTTP; Mon, 2 Jun 2014 04:48:49 -0700 (PDT)
From: Yoriyuki Yamagata <yoriyuki.y@gmail.com>
Date: Mon, 2 Jun 2014 20:48:49 +0900
Message-ID: <CALdQWQ6fdaCMCG-dDn+Khva1nPL=mcNDq2uLS-d60UYmMM1Eeg@mail.gmail.com>
To: Caml List <caml-list@inria.fr>
Content-Type: multipart/alternative; boundary=001a11c303d4b3d8ec04fad8fb27
Subject: [Caml-list] Why AVL-tree?

--001a11c303d4b3d8ec04fad8fb27
Content-Type: text/plain; charset=UTF-8

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/ <http://yoriyuki.info/>*

--001a11c303d4b3d8ec04fad8fb27
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">Hi, list,<div><br></div><div>Just from the curiosity, why =
balanced binary trees used in Set and Map are AVL-trees, not their alternat=
ive, say, red-black trees? =C2=A0Is there a deep reason for it, or just a h=
istorical one?</div>

<div><br></div><div>Best,<br>-- <br><div dir=3D"ltr">Yoriyuki Yamagata<br><=
u><a href=3D"http://yoriyuki.info/">http://yoriyuki.info/</a></u></div>
</div></div>

--001a11c303d4b3d8ec04fad8fb27--