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

[Tom Ridge <tom.j.ridge+list@googlemail.com>]

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

I am working on a B+ tree. We are focusing on the verification in Isabelle,
but it would not be too difficult maybe to get some working OCaml code
together. As Frederic says, maybe you just want a binary tree?

On 5 November 2015 at 10:34, Frédéric Bour <frederic.bour@lakaban.net>
wrote:

> 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: 2709 bytes --]