Goswin von Brederlow <goswin-...@web.de> wrote: > Francois Berenger <beren...@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. -- 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
