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 HAA06082; Wed, 12 Nov 2003 07:51:18 +0100 (MET) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id HAA05960 for ; Wed, 12 Nov 2003 07:51:17 +0100 (MET) Received: from herd.plethora.net (herd.plethora.net [205.166.146.1]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id hAC6pG126980 for ; Wed, 12 Nov 2003 07:51:16 +0100 (MET) Received: from bhurt.plethora.net (bhurt.plethora.net [205.166.146.49]) by herd.plethora.net (8.11.6/8.10.1) with ESMTP id hAC6ouC07099; Wed, 12 Nov 2003 00:50:57 -0600 (CST) Date: Wed, 12 Nov 2003 01:50:00 -0600 (CST) From: Brian Hurt X-X-Sender: bhurt@localhost.localdomain To: "Harrison, John R" cc: Ocaml Mailing List Subject: RE: [Caml-list] Efficient and canonical set representation? In-Reply-To: <3C4C3612EC443546A33E57003DB4F0F914C277@orsmsx409.jf.intel.com> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 equality:01 nov:01 tree:02 tree:02 comparison:02 canonical:03 wrote:03 redirect:95 let:04 structural:04 structural:04 efficient:05 obvious:06 brian:06 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Tue, 11 Nov 2003, Harrison, John R wrote: > | I've been batting around ideas for ways to do balanced trees so that no > | matter what order you add things, you always get the same tree. But even > | assuming you could do this, doing a structural compare is still O(N). So > | you might as well let the trees be different. > > Right, but see my second message --- I'm only interested in canonicity > up to structural equality and I'm happy with O(N) comparison. So it's > just the "no matter what order you add things you get the same tree" > property that I care about. But it's not yet obvious to me whether I > can even achieve that much. > It feels like that can be done, at the cost of an occassional O(N) "massive rebalancing". Well, it certainly can be done with an O(N) insert/delete. I'll think about it a bit. -- "Usenet is like a herd of performing elephants with diarrhea -- massive, difficult to redirect, awe-inspiring, entertaining, and a source of mind-boggling amounts of excrement when you least expect it." - Gene Spafford Brian ------------------- 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