Re: [Caml-list] Fwd: interval trees

[Goswin von Brederlow <goswin-v-b@web.de>]

Francois Berenger <berenger@riken.jp> writes:

> Hello,
>
> I did a naive implementation of interval trees for float intervals.
>
> It is available here:
> https://github.com/HappyCrow/interval-tree
>
> I wonder if it is possible to construct the trees in a tail recursive
> fashion. Maybe I knew how to do this when I was still at university.
>
> Regards,
> Francois.

| Node of
   (* x_mid left_list right_list left_tree right_tree *)
      float * interval list * interval list * interval_tree * interval_tree

Why interval list? You only need a single interval in leafes and none in
other nodes (although it can help to store min and max in each node).

You are also missing insert and remove operations, which is the actually
hard part in this. Inserting an interval might require merging the
rightmost interval left of the root and the leftmost interval right of
the root. So you would have 2 removals and one insertion of a combined
interval, which complicates balancing the whole thing efficiently.

That is the part I'm struggling with.

MfG
        Goswin