Graphics Reference
In-Depth Information
Definition.
The data structure S(I) consisting of the annotated tree T(S) is called a
segment tree
.
Figure 17.4 shows a segment tree. Algorithm 17.3.2 shows how a segment tree is
used for a query. We construct the segment tree by first sorting the endpoints of the
intervals and use this ordering to build a balanced binary search tree for the ele-
mentary intervals. We also compute the intervals E(
n
) for all the nodes
n
. Then the
intervals from I are inserted one at a time in the appropriate lists associated to the
nodes
n
using Algorithm 17.3.3.
17.3.4 Theorem.
The segment tree associated to a set of n intervals uses O(n log
2
n)
storage and can be built in time O(n log
2
n). If there are k intervals that contain the
query point, we can report them in time O(log
2
n + k).
Figure 17.4.
A segment tree.
procedure
SegmentTreeQuery (
segment tree
S,
real
c)
begin
Report all the intervals in I (Root (S));
if
NotALeaf (S)
then
if
c ΠE (Root (LeftSubtree (S)))
then
SegmentTreeQuery (LeftSubtree (S),c);
else
SegmentTreeQuery (RightSubtree (S),c);
end
;
Algorithm 17.3.2.
The segment tree query algorithm.
