Computational Geometry Topics - Computer Graphics and Geometric Modeling - page 695

procedure 1dRangeQuery ( binary tree T, real a, b)
begin
binary tree splitT;

splitT := SplitNode (T, a, b);
if IsLeaf (splitT)
then check if we need to print splitT r
else

begin
T := LeftSubtree (splitT);
while NotALeaf (T) do
if a £ T r
then
begin
PrintSubTree (RightSubtree (T));
T := LeftSubtree (T);

end
else T := RightSubtree (T);
Check if we need to print T r ;

T := RightSubtree (splitT);
Do a similar traversal as we did for the left subtree, except that
we print leaves of left subtrees;

end

end ;

Algorithm 17.2.2. A 1d range query algorithm.

We reduce the solution to Problem 2 to two one-dimensional problems. Let p i =
(x i ,y i ). Assume that all the x- and y-coordinates of our points are distinct. We need
this assumption for the binary search trees we build, but shall show how to get rid of
this assumption later.

Step 1. Create a balanced binary search tree T for the x-coordinates x i like in the
solution to Problem 1. This will enable us to find all the points of S whose x-coordinates
lie in the correct range. Of course, their y-coordinates may not be in range.

Step 2. If n is a node of T, let P( n ) be all the points of S that are leaves in the subtree
of T with root n . Store at n a pointer to the balanced binary search tree T( n ) based
on the y-coordinates of the points in P( n ), except that we also store the points p i at
the leaves not just simply their y-coordinates.

Definition. The data structure consisting of the tree T together with the associated
trees T( n ) is called a range tree .