Re: [Caml-list] Re: Set and Map question

[Jean-Christophe Filliatre <Jean-Christophe.Filliatre@lri.fr>]

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