Version française
Home     About     Download     Resources     Contact us    

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

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 Archives:
Bug reports: FAQ:
Beginner's list: