Re: [Caml-list] Fwd: interval trees

[John Carr <jfc@mit.edu>]

Goswin von Brederlow <goswin-v-b@web.de> wrote:

> Francois Berenger <berenger@riken.jp> writes:
> >
> > let rec interval_tree intervals =
> >   match intervals with
> >       [] -> Empty
> >     | _ ->
> >         let x_mid = median intervals in
> >         let left, mid, right = partition intervals x_mid in
> >         let left_list = L.sort leftmost_bound_first mid in
> >         let right_list = L.sort rightmost_bound_first mid in
> >         Node (x_mid,
> >               left_list, right_list,
> >               interval_tree left, interval_tree right)
> >
> > I'm afraid my program could crash on a very long list of intervals.
> 
> Each recursion halves the lists, right? That means you need a very very
> very long list to exceed the recursion depth.

How good is median selection?  If it works like quicksort, approximating
the median, typical stack depth is logarithmic and worst case stack
depth is linear.  If median selection is precise, creating a balanced
tree, I wouldn't worry about stack depth.