Re: [Caml-list] Fwd: interval trees

[Edgar Friendly <thelema314@gmail.com>]

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

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
>
>

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