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 OAA22720; Mon, 20 Sep 2004 14:54:38 +0200 (MET DST) 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 OAA21318 for ; Mon, 20 Sep 2004 14:54:37 +0200 (MET DST) Received: from ext.lri.fr (ext.lri.fr [129.175.15.4]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id i8KCsbxw029654 (version=TLSv1/SSLv3 cipher=EDH-RSA-DES-CBC3-SHA bits=168 verify=NO) for ; Mon, 20 Sep 2004 14:54:37 +0200 Received: from localhost (localhost [127.0.0.1]) by ext.lri.fr (Postfix) with ESMTP id 0F7BA19E7F5; Mon, 20 Sep 2004 14:54:37 +0200 (CEST) Received: from ext.lri.fr ([127.0.0.1]) by localhost (ext.lri.fr [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 29438-10; Mon, 20 Sep 2004 14:54:37 +0200 (CEST) Received: from smtp.lri.fr (serveur3-5 [129.175.3.5]) by ext.lri.fr (Postfix) with ESMTP id F18D719E7EF; Mon, 20 Sep 2004 14:54:36 +0200 (CEST) Received: from pc8-142 (pc8-142 [129.175.8.142]) by smtp.lri.fr (Postfix) with ESMTP id CD055CEE10; Mon, 20 Sep 2004 14:54:35 +0200 (CEST) Received: from filliatr by pc8-142 with local (Exim 3.36 #1 (Debian)) id 1C9Ngi-0006AS-00; Mon, 20 Sep 2004 14:54:36 +0200 MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit Message-ID: <16718.54028.37113.319426@gargle.gargle.HOWL> Date: Mon, 20 Sep 2004 14:54:36 +0200 To: caml-list@pauillac.inria.fr Cc: Richard Jones , Brian Hurt Subject: Re: [Caml-list] Re: Set and Map question In-Reply-To: References: <20040920081708.GA2792@annexia.org> X-Mailer: VM 7.18 under Emacs 21.3.1 From: Jean-Christophe Filliatre X-Virus-Scanned: by amavisd-new at lri.fr X-Miltered: at concorde with ID 414ED30D.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 filliatre:01 filliatre:01 lri:01 2004:99 red-black:01 red-black:01 truncate:01 lri:01 filliatr:01 linked:01 linked:01 computed:01 black:98 black:98 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Igor Pechtchanski writes: > On Mon, 20 Sep 2004, Richard Jones wrote: > > > On Sun, Sep 19, 2004 at 11:02:44PM -0500, Brian Hurt wrote: > > > The code is actually fairly easy. Take the length of the list. Subtract > > > one for the root node. The first (n-1)/2 elements are in the left hand > > > subtree, the last n-1-((n-1)/2) elements are in the right subtree. > > > > Wouldn't you have to iterate over the list when implementing this? > > What I mean to say is that this would work if you had a pre-sorted > > Array, but not a linked List. ? > > Did the question mention anything about the space used by the algorithm? > If one is allowed O(n) temp space, then simply converting the sorted > linked List into a temp array as the first step will keep the algorithm > O(n) (constant factors aside). One would need a constant-time-access data There is no need converting the list into an array. Once the length is computed (with a single traversal of the list), it is possible to build the tree with only another traversal of the list. Here is for instance how to build a red-black tree from a (reverse) sorted list of elements: =========================================================================== (*s Building a red-black tree from a sorted list in reverse order. The result is a complete binary tree, where all nodes are black, except the bottom line which is red. *) let log2 n = truncate (log (float n) /. log 2.) let of_list sl = let rec build sl n k = if k = 0 then if n = 0 then Empty, sl else match sl with | [] -> assert false | x :: sl -> Red (Empty, x, Empty), sl else let n' = (n - 1) / 2 in match build sl n' (k - 1) with | _, [] -> assert false | l, x :: sl -> let r, sl = build sl (n - n' - 1) (k - 1) in Black (r, x, l), sl in let n = List.length sl in fst (build sl n (log2 n)) =========================================================================== The key idea is to return the tree together with the list of unused elements in the list. regards, -- Jean-Christophe Filliātre (http://www.lri.fr/~filliatr) ------------------- 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