English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

Browse thread
[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 (08:35)
From: Diego Olivier Fernandez Pons <Diego.FERNANDEZ_PONS@e...>
Subject: Re: [Caml-list] Re: Set and Map question

> 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