Re: [Caml-list] Fwd: interval trees

[Francois Berenger <berenger@riken.jp>]

On 02/16/2012 02:22 AM, Edgar Friendly wrote:
> 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`

Precisely, it is:
type: interval_tree -> float -> 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,

That would be a nice optimization for queries indeed.

At the moment, I'm more concerned about the program blowing up
during tree construction.

Regards,
F.

 > 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 <mailto:goswin-v-b@web.de>> wrote:
>
>     Francois Berenger <berenger@riken.jp <mailto: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
>
>