I struggled with this too, but if you read the wikipedia page http://en.wikipedia.org/wiki/Interval_tree, he's implemented a centered interval tree.  Yes, there's a lot of complications needed to insert and remove, but what he's done works for static interval trees.

His lookup function is `int -> interval list`, not `int -> bool`, so he must keep all the intervals that overlap the center point so he can return them.  It's useful to have them sorted by left endpoint as well as right endpoint.  I might have used arrays for them instead of lists so that binary search is doable, but if they're small, it doesn't matter much.

E.

On Wed, Feb 15, 2012 at 10:21 AM, Goswin von Brederlow <goswin-v-b@web.de> wrote:
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

--
Caml-list mailing list.  Subscription management and archives:
https://sympa-roc.inria.fr/wws/info/caml-list
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs