From: Beman Dawes (bdawes_at_[hidden])
Date: 2001-12-31 16:48:12
At 10:07 AM 12/31/2001, 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 a one-dimensional case of the general n-dimensional R-tree
(or R*tree or R+tree refinements) used for spatial search. Although I've
never used anything other than a B-tree, I'm pretty sure you can implement
an R-/*/+tree on top of any kind of binary or multi-way underlying tree
structure.
By the way, an ordering other than on start position can have dramatically
better performance (at least for multi-dimensional cases).
See the book Spatial Databases by Rigaux, Scholl, and Voisard, beginning
around page 238. ISBN 1-55860-588-6.
--Beman