Graphics Reference
In-Depth Information
Incidentally, the left and right subtrees of each interior node
n
of the tree T can
be thought of as representing ranges. If the node has the value s and its parent
the value t, then [-•,s] and [s,t] are the ranges of the left and right subtree of
n
,
respectively.
By linking all the leaves of T together, it is easy to see that the time complexity of
Problem 1 is O(log
2
n + k), where k is the number of elements of
S
that lie in [a,b].
The links take up additional space and one can do without them using a recursive
algorithm that traverses all the subtrees “between” leaves
n
a
and
n
b
. In Figure 17.1,
the nodes that have to be traversed, other than those on the path to
n
a
and
n
b
, are
shown in black. Because the ideas behind implementing this recursive algorithm will
be needed later, we shall describe the algorithm. An important location we have to
find is the node where the paths from the root of T to
n
a
and
n
b
split. We shall call
this the
splitting node
. For example, the splitting nodes for the intervals [25,72] and
[25,40] are indicated in Figure 17.1. Let T
r
denote the number stored at the root of a
tree T. Algorithm 17.2.1 finds the splitting node. After we find the splitting node for
our range problem, then we simply make one pass from that node to
n
a
, printing the
leaves of all the
right
subtrees of the nodes we encounter, and another pass from that
node to
n
b
, printing the leaves of all the
left
subtrees of the nodes we encounter. The
leaves
n
a
and
n
b
themselves have to be checked separately to see if the values they
hold are part of our range. Algorithm 17.2.2 describes the whole range query process.
Summarizing we get
17.2.1 Theorem.
Given a set of n real numbers, these numbers can be stored in a
balanced binary search tree that can be constructed in time O(n log
2
n) using O(n)
space. Interval queries can be made in time O(log
2
n + k), where k is number of real
numbers in our set that satisfy the query.
Proof.
For more details see [BKOS97].
Next, we look at the corresponding two-dimensional problem for finding points
in certain ranges.
Problem 2.
Assume that
S
= {
p
1
,
p
2
,...,
p
n
} is a fixed set of n points in
R
2
. Given a
rectangle (or “window”) [a,b] ¥ [c,d], which of the
p
i
lies in this rectangle?
binary tree function
SplitNode (
binary tree
T,
real
a, b)
begin
while
NotALeaf (T)
and
((b £ T
r
)
or
(a > T
r
))
do
if
b £ T
r
then
T := LeftSubtree (T)
else
T := RightSubtree (T);
return
T;
end
;
Algorithm 17.2.1.
Finding the splitting node.
