From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id RAA28085; Wed, 12 Nov 2003 17:17:58 +0100 (MET) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id RAA27852 for ; Wed, 12 Nov 2003 17:17:56 +0100 (MET) Received: from shiva.jussieu.fr (shiva.jussieu.fr [134.157.0.129]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id hACGHt117514 for ; Wed, 12 Nov 2003 17:17:55 +0100 (MET) Received: from ibm3.cicrp.jussieu.fr (ibm3.cicrp.jussieu.fr [134.157.15.3]) by shiva.jussieu.fr (8.12.10/jtpda-5.4) with ESMTP id hACGHoqY052218 ; Wed, 12 Nov 2003 17:17:51 +0100 (CET) Received: from ibm1.cicrp.jussieu.fr (ibm1.cicrp.jussieu.fr [134.157.15.1]) by ibm3.cicrp.jussieu.fr (8.8.8/jtpda/mob-V8) with ESMTP id RAA45174 ; Wed, 12 Nov 2003 17:16:54 +0100 Received: from localhost (fernande@localhost) by ibm1.cicrp.jussieu.fr (8.8.8/jtpda/mob-v8) with ESMTP id RAA2007050 ; Wed, 12 Nov 2003 17:16:53 +0100 Date: Wed, 12 Nov 2003 17:16:52 +0100 (NFT) From: Diego Olivier Fernandez Pons To: "Harrison, John R" cc: caml-list@inria.fr Subject: RE: [Caml-list] Efficient and canonical set representation? In-Reply-To: <3C4C3612EC443546A33E57003DB4F0F914C273@orsmsx409.jf.intel.com> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Antivirus: scanned by sophie at shiva.jussieu.fr X-Loop: caml-list@inria.fr X-Spam: no; 0.00; pons:01 pons:01 etu:99 caml-list:01 red-black:01 logarithmic:01 fernandez:01 fernandez:01 olivier:02 olivier:02 tree:02 tree:02 canonical:03 somewhere:04 efficiency:05 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Bonjour, > Is it just a coincidence that the numerous varieties of balanced > tree (AVL, 2-3-4, red-black, ...) all seem to be non-canonical? Or > is it essential to their efficiency? (Perhaps this is a question for > another forum.) It is not a coincidence. I remember having read somewhere that it could be proven that if a balanced tree (based on comparisons) did not have enough different representations of a same set, then the insertion could not be done in logarithmic time. Diego Olivier ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners