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

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

----- Original Message -----
From: "Nathan Myers" <ncm-yahoospam_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Monday, December 31, 2001 11:16 AM
Subject: [boost] extent trees (was Re: new component, extent_set<>)

> "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.

Do you mean the implementation? Not so much work, really. I did it once
using STLPort's tree implementation as the basis.

> 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.

As Howard pointed out, RB-trees don't require evaluating Compare() during
rebalance. In fact, if rebalance caused calls to Compare(), we couldn't
implement the standard's exception guarantees for associative containers
with RB-trees. The HP and SGI implementations don't call Compare() during
rebalance, either.

In the interval tree case, however, you obviously need to call the compare
function for the interval endpoints to update the maximum endpoint cache on
each node.

-Dave