Interval, Segment, Range, and Priority Search Trees:Introduction and Interval Trees

Introduction

In this chapter we introduce four basic data structures that are of fundamental importance and have many applications as we will briefly cover them in later sections. They are interval trees, segment trees, range trees, and priority search trees. Consider for example the following problems. Suppose we have a set of iso-oriented rectangles in the planes. A set of rectangles are said to be iso-oriented if their edges are parallel to the coordinate axes. The subset of iso-oriented rectangles define a clique, if their common intersection is nonempty. The largest subset of rectangles whose common intersection is non-empty is called a maximum clique. The problem of finding this largest subset with a non-empty common intersection is referred to as the maximum clique problem for a rectangle intersection graph[14, 16].

∗ The k-dimensional, k ≥ 1, analog of this problem is defined similarly. In 1-dimensional case we will have a set of intervals on the real line, and an interval intersection graph, or simply interval graph. The maximum clique problem for interval graphs is to find a largest subset of intervals whose common intersection is non-empty. The cardinality of the maximum clique is sometimes referred to as the density of the set of intervals.

The problem of finding a subset of objects that satisfy a certain property is often referred to as searching problem. For instance, given a set of numbers S = {x1, x2,... , xn}, where

xi ∈ 3i, i = 1, 2,... , n, the problem of finding the subset of numbers that lie between a range [f, r], i.e., F = {x ∈ S|f ≤ x ≤ r}, is called a (1D) range search problem[5, 22].

To deal with this kind of geometric searching problem, we need to have appropriate data structures to support efficient searching algorithms. The data structure is assumed to be static, i.e., the input set of objects is given a priori, and no insertions or deletions of the objects are allowed. If the searching problem satisfies decomposability property, i.e., if they are decomposable† , then there are general dynamization schemes available[21], that can be used to convert static data structures into dynamic ones, where insertions and deletions of objects are permitted. Examples of decomposable searching problems include the membership problem in which one queries if a point p in S. Let S be partitioned into two subsets S1 and S2, and Member(p, S) returns yes, if p ∈ S, and no otherwise. It is easy to see that Member(p, S)= OR(Member(p, S1), Member(p, S2)), where OR is a boolean operator.

Interval Trees

Consider a set S of intervals, S = {Ii|i = 1, 2,... , n}, each of which is specified by an ordered pair, Ii = [fi, ri], fi, ri ∈ 3i, fi ≤ ri,i = 1, 2,... , n.

An interval tree[8, 9], Interval Tree(S), for S is a rooted augmented binary search tree, in which each node v has a key value, v.key, two tree pointers v.left and v.right to the left and right subtrees, respectively, and an auxiliary pointer, v.aux to an augmented data

structure, and is recursively defined as follows:

• The root node v associated with the set S, denoted Interval Tree root(S), has key value v.key equal to the median of the 2 × |S| endpoints. This key value v.key divides S into three subsets Se, Sr and Sm, consisting of sets of intervals lying totally to the left of v.key, lying totally to the right of v.key and containing v.key respectively. That is, Se = {Ii|ri < v.key}, Sr = {Ij |v.key < fj } and Sm = {Ik |fk ≤ v.key ≤ rk }.

• Tree pointer v.left points to the left subtree rooted at Interval Tree root(Se), and tree pointer v.right points to the right subtree rooted at Interval Tree root(Sr ).

• Auxiliary pointer v.aux points to an augmented data structure consisting of two sorted arrays, SA(Sm .left ) and SA(Sm .right ) of the set of left endpoints of the intervals in Sm and the set of right endpoints of the intervals in Sm respectively. That is, Sm.left = {fi|Ii ∈ Sm} and Sm.right = {ri|Ii ∈ Sm}.

Construction of Interval Trees

The following is a pseudo code for the recursive construction of the interval tree of a set S of n intervals. Without loss of generality we shall assume that the endpoints of these n intervals are all distinct. See Fig. 18.1(a) for an illustration.

function Interval Tree(S) /* It returns a pointer v to the root, Interval Tree root(S), of the interval tree for a set S of intervals. */

Input: A set S of n intervals, S = {Ii|i = 1, 2,... , n} and each interval Ii = [fi, ri], where fi and ri are the left and right endpoints, respectively of Ii, fi, ri ∈ 3i, and fi ≤ ri,i = 1, 2,... , n.

Output: An interval tree, rooted at Interval Tree root(S).

Method:

1. if S = ∅, return nil.

2. Create a node v such that v.key equals x, where x is the middle point of the set of endpoints so that there are exactly |S|/2 endpoints less than x and greater than x respectively. Let Se = {Ii|ri < x}, Sr = {Ij |x < fj } and Sm = {Ik |fk ≤ x ≤ rk }.

3. Set v.left equal to Interval Tree(Se).

4. Set v.right equal to Interval Tree(Sr )

5. Create a node w which is the root node of an auxiliary data structure associated with the set Sm of intervals, such that w.left and w.right point to two sorted arrays, SA(Sm.left ) and SA(Sm.right ), respectively. SA(Sm .left ) denotes an array of left endpoints of intervals in Sm in ascending order, and SA(Sm .right ) an array of right endpoints of intervals in Sm in descending order.

6. Set v.aux equal to node w.

Note that this recursively built interval tree structure requires O(n) space, where n is the cardinality of S, since each interval is either in the left subtree, the right subtree or the middle augmented data structure.

Example and Its Applications

Fig. 18.1(b) illustrates an example of an interval tree of a set of intervals, spread out as shown in Fig. 18.1(a).

The interval trees can be used to handle quickly queries of the following form.

Enclosing Interval Searching Problem [11, 15] Given a set S of n intervals and a query point, q, report all those intervals containing q, i.e., find a subset F ⊆ S such that F = {Ii|fi ≤ q ≤ ri}.

Overlapping Interval Searching Problem [4, 8, 9] Given a set S of n intervals and a query interval Q, report all those intervals in S overlapping Q, i.e., find a subset F ⊆ S such that F = {Ii|Ii ∩ Q j= ∅}.

The following pseudo code solves the Overlapping Interval Searching Problem in O(log n) + |F | time. It is invoked by a call to Overlapping Interval Search(v, Q, F ), where v is Interval Tree root(S), and F , initially set to be ∅, will contain the set of intervals over- lapping query interval Q.

procedure Overlapping Interval Search(v, Q, F )

Input: A set S of n intervals, S = {Ii|i = 1, 2,... , n} and each interval Ii = [fi, ri], where fi and ri are the left and right endpoints, respectively of Ii, fi, ri ∈ 3i, and fi ≤ ri,i = 1, 2,... ,n and a query interval Q = [f, r], f,r ∈ 3i.

Output: A subset F = {Ii|Ii ∩ Q j= ∅}.

Method:

It is obvious to see that an interval I in S overlaps a query interval Q = [f, r] if (i) Q contains the left endpoint of I, (ii) Q contains the right endpoint of I, or (iii) Q is totally contained in I. Step 3 reports those intervals I that contain a point v.key which is also contained in Q. Step 4 reports intervals in either case (i) or (iii) and Step 5 reports intervals

in either case (ii) or (iii).

Note the special case of procedure Overlapping Interval Search(v, Q, F ) when we set the query interval Q = [f, r] so that its left and right endpoints coincide, i.e., f = r will report all the intervals in S containing a query point, solving the Enclosing Interval Searching Problem.

However, if one is interested in the problem of finding a special type of overlapping intervals, e.g., all intervals containing or contained in a given query interval[11, 15], the interval tree data structure does not necessarily yield an efficient solution. Similarly, the interval tree does not provide an effective method to handle queries about the set of intervals, e.g., the maximum clique, or the measure, the total length of the union of the intervals[10, 17].

We conclude with the following theorem.

THEOREM 18.1 The Enclosing Interval Searching Problem and Overlapping Interval Searching Problem for a set S of n intervals can both be solved in O(log n) time (plus time for output) and in linear space.