Re: [boost] Re: new component, extent_set<>

From: David Abrahams (david.abrahams_at_[hidden])
Date: 2001-12-31 10:07:30

A data structure I've needed (and used) from time to time which I presume is
different from everything described so far in this thread is an "interval
tree". An interval tree is an RB-tree of intervals sorted on the start
position of each interval, where each node contains an additional record of
the maximum end position of all intervals in the subtree rooted at that
node. The intervals are allowed to overlap. It is possible to efficiently
enumerate all intervals in the tree that overlap any given interval, for
example.

-Dave