This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

[Caml-list] Set and Map question
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2004-09-20 (12:54) From: Jean-Christophe Filliatre Subject: Re: [Caml-list] Re: Set and Map question
```
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

```