extent trees (was Re: new component, extent_set<>)

From: Nathan Myers (ncm-yahoospam_at_[hidden])
Date: 2001-12-31 11:16:59

"David Abrahams" wrote:
> 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.

That sounds like work.  

BTW, RB-trees are far from the last word in balanced tree design.  I hope
that someday our STL containers can be built with better tree designs.
Some, e.g., don't require evaluating Compare()(a,b) during rebalance 
operations, for example.  

BTW^2 (speaking of work), trees keyed on strings group entries with identical
prefixes together, so that as you walk down them or rebalance them you are
comparing the same substrings over and over before you get to the parts that
differ.   Specializing trees for the case of string keys to identify where
the difference begins, should speed up string-keyed trees dramatically.
(I think the extremum of such an optimization is a lexicographic tree.)

Nathan Myers
ncm_at_[hidden]