Re: [Caml-list] Do we have a B-tree implementation in ocaml?

["Frédéric Bour" <frederic.bour@lakaban.net>]

[-- Attachment #1: Type: text/plain, Size: 1460 bytes --]

If I understand well, you want an efficient rank function on a 
sequence, you are not particularly interested in B-trees.

I have an implementation of balanced trees you might be interested into:

  https://github.com/def-lkb/grenier/blob/master/baltree/bt1.mli

It is a binary tree with a smart constructor to ensure only balanced 
trees are built.
Beside that, no other constraints are applied. In particular these are 
not search trees although those can easily be implemented on top.

O(1) access to the size (number of items) is provided, and as such an 
O(log n) rank function.

Performance is also quite competitive: although I did not push the code 
yet, I implemented Map and Set from the standard library using these 
trees. On a small set of benchmarks I ran, these were at worst 10% 
slower than the standard ones.


On Wed, Nov 4, 2015 at 6:39 PM, Francois Berenger 
<francois.berenger@inria.fr> wrote:
> Hello,
> 
> I am looking for even a simple implementation with at
> least the following operations:
> 
> insert/add, remove, mem/contains and at_rank.
> 
> The at_rank is especially important since it is inefficient
> to implement it using fold in a set like the ones from the stdlib.
> 
> Thanks a lot,
> F.
> 
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa.inria.fr/sympa/arc/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs

[-- Attachment #2: Type: text/html, Size: 1961 bytes --]