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 OAA20411; Mon, 20 Sep 2004 14:41:32 +0200 (MET DST) 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 OAA19987 for ; Mon, 20 Sep 2004 14:41:31 +0200 (MET DST) Received: from slinky.cs.nyu.edu (SLINKY.CS.NYU.EDU [128.122.20.14]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id i8KCfU6w008420 for ; Mon, 20 Sep 2004 14:41:31 +0200 Received: from localhost (localhost [127.0.0.1]) by slinky.cs.nyu.edu (8.12.10+Sun/8.12.10) with ESMTP id i8KCfQoQ015748; Mon, 20 Sep 2004 08:41:27 -0400 (EDT) Date: Mon, 20 Sep 2004 08:41:26 -0400 (EDT) From: Igor Pechtchanski Reply-To: caml-list@pauillac.inria.fr To: Richard Jones cc: Brian Hurt , caml-list@pauillac.inria.fr Subject: Re: [Caml-list] Re: Set and Map question In-Reply-To: <20040920081708.GA2792@annexia.org> Message-ID: References: <20040920081708.GA2792@annexia.org> Importance: Normal MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Scanned-By: MIMEDefang 2.39 X-Miltered: at nez-perce with ID 414ECFFA.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; nyu:99 caml-list:01 2004:99 nyu:99 ,,,:99 linked:01 linked:01 sep:01 sep:01 node:02 tree:02 --':96 wrote:03 wrote:03 algorithm:03 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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 structure anyway, to build a balanced tree bottom-up in a functional way. Igor -- http://cs.nyu.edu/~pechtcha/ |\ _,,,---,,_ pechtcha@cs.nyu.edu ZZZzz /,`.-'`' -. ;-;;,_ igor@watson.ibm.com |,4- ) )-,_. ,\ ( `'-' Igor Pechtchanski, Ph.D. '---''(_/--' `-'\_) fL a.k.a JaguaR-R-R-r-r-r-.-.-. Meow! "Happiness lies in being privileged to work hard for long hours in doing whatever you think is worth doing." -- Dr. Jubal Harshaw ------------------- 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