Bonjour,

> Yes, sorry, sorted. I know it is possible, I was wondering if it was
> implemented.

I never understood how worked those functions building a balanced
search tree from a sorted list in O(n) _without_ first counting the
number of elements in the list.

Hence it is not implemented in Baire. As far as I know, there is no
Caml implementation of any of them either (they all iter on the list
applying O(log n) insertion function) but I may be wrong.

SML/NJ standard library has a O(n) 'from_ordered_list' function for
red-black trees. SML/NJ implementation of red-black trees uses zippers
to handle insertion and deletion operations. It may be difficult to
understand if you are not used to them.

Ralf Hinze wrote a good paper on red-black trees (Constructing
red-black trees, WAAAPL'99, available from his website). It explains
how to implement 'from_ordered_list' in O(n) and most of existent
functional implementations must be more or less based on it.


        Diego Olivier

-------------------
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