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

Priority Search Trees

The priority search tree was originally introduced by McCreight[19]. It is a hybrid of two data structures, binary search tree and a priority queue.[13] A priority queue is a queue and supports the following operations: insertion of an item and deletion of the minimum (highest priority) item, so called delete min operation. Normally the delete min operation takes constant time, while updating the queue so that the minimum element is readily accessible takes logarithmic time. However, searching for an element in a priority queue will normally take linear time. To support efficient searching, the priority queue is modified to be a priority search tree. We will give a formal definition and its construction later. As the priority search tree represents a set S of elements, each of which has two pieces of information, one being a key from a totally ordered set, say the set 3i of real numbers, and the other being a notion of priority, also from a totally ordered set, for each element, we can model this set S as a set of points in 2-dimensional space. The x- and y-coordinates of a point p represent thekey  and the priority respectively. For instance, consider a set of jobs S = {J1, J2,..., Jn}, each of which has a release time ri ∈3i and a priority pi ∈ 3i,i = 1, 2,... , n. Then each jobJi c an be represented as a point q such that q.x = ri, q.y = pi.

The priority search tree can be used to support queries of the form, find, among a set S of n points, the point p with minimum p.y such that its x-coordinate lies in a given range [f, r], i.e., f ≤ p.x ≤ r. As can be shown later, this query can be answered in O(log n) time.

Construction of Priority Search Trees

As before, the root node, Priority Search Tree root(S), represents the entire set S of points. Each node v in the tree will have a key v.key, an auxiliary data v.aux containing the index of the point and its priority, and two pointers v.left and v.right to its left and right subtrees respectively such that all the key values stored in the left subtree are less than v.key, and all the key values stored in the right subtree are greater than v.key. The following is a pseudo code for the recursive construction of the priority search tree of a set S of n points in 3i2. See Fig. 18.5(a) for an illustration.

Thus, Priority Search Tree root(S) is a minimum heap data structure with respect to the y-coordinates, i.e., the point with minimum y-coordinate can be accessed in constant time, and is a balanced binary search tree for the x-coordinates. Implicitly the root node v is associated with an x-range [xe, xr ] representing the span of the x-coordinate values of all the points in the whole set S. The root of the left subtree pointed to by v.left is associated with the x-range [xe , v.key] representing the span of the x-coordinate values of all the points in the set Se and the root of the right subtree pointed to by v.right is associated with the x- range [v.key, xr ] representing the span of the x-coordinate values of all the points in the set Sr . It is obvious that this algorithm takes O(n log n) time and linear space. We summarize this in the following.

THEOREM 18.7 The priority search tree for a set S of n points in 3i2 can be constructed in O(n log n) time and linear space.

Examples and Its Applications

Fig. 18.5 illustrates an example of a priority search tree of the set of points. Note that the root node contains p6 since its y-coordinate value is the minimum.

We now illustrate a usage of the priority search tree by an example. Consider a so- called grounded 2D range search problem for a set of n points in the plane. As defined in Section 18.4.2, a 2D range search problem is to find all the points p ∈ S such that p.x lies in an x-range [xe , xr ], xe ≤ xr and p.y lies in a y-range [ye, yr ]. When the y-range is of the

form [−∞, yr ] then the 2D range is referred to as grounded 2D range or sometimes as 1.5D range, and the 2D range search problem as grounded 2D range search or 1.5D range search problem.

Grounded 2D Range Search Problem Given a set S of n points in the plane 3i , with preprocessing allowed, find the subset F of points whose x- and y- coordinates satisfy a grounded 2D range query of the form [xe, xr ]×[−∞, yr ], xe, xr , yr ∈ 3i, xe ≤ xr .

The following pseudo code solves this problem optimally. We assume that a priority search tree for S has been constructed via procedure Priority Search Tree(S). The answer will be obtained in F via an invocation to Priority Search Tree Range Search(v, xe, xr , yr ,F ), where v is Priority Search Tree root(S).

procedure Priority Search Tree Range Search(v, xe, xr , yr ,F ) /* v points to the root of the tree, F is a queue and set to nil initially. */

Input: A set S of n points, {p1, p2,... , pn}, in 3i2, stored in a priority search tree, Priority Search Tree(S) pointed to by Priority Search Tree root(S) and a 2D grounded range [xe , xr ] × [−∞, yr ], xe , xr , yr ∈ 3i, xe ≤ xr .

Output: A subset F ⊆ S of points that lie in the 2D grounded range, i.e., F = {p ∈ S|xe ≤ p.x ≤ xr and p.y ≤ yr }.

Method:

1. Start from the root v finding the first split-node vsplit such that vsplit .x lies in the x-range [xe , xr ].

2. For each node u on the path from node v to node vsplit if the point pu.aux lies in range [xe, xr ] × [∞, yr ] then report it by (pu.aux ⇒ F ).

3. For each node u on the path of xe in the left subtree of vsplit do if the path goes left at u then Priority Search Tree 1dRange Search(u.right , yr ,F ).

4. For each node u on the path of xr in the right subtree of vsplit do if the path goes right at u then Priority Search Tree 1dRange Search(u.left , yr ,F ).

procedure Priority Search Tree 1dRange Search(v, yr,F ) basically retrieves all the points stored in the priority search tree rooted at v such that their y-coordinates are all less than and equal to yr . The search terminates at the node u whose associated point has a y- coordinate greater than yr , implying all the nodes in the subtree rooted at u satisfy this property. The amount of time required is proportional to the output size. Thus we conclude that THEOREM 18.8 The Grounded 2D Range Search Problem for a set S of n points in the plane 3i2 can be solved in time O(log n) plus time for output, with a priority search tree structure for S that requires O(n log n) time and O(n) space.

Note that the space requirement for the priority search tree in linear, compared to that of a 2D-range tree, which requires O(n log n) space. That is, the Grounded 2D Range Search Problem for a set S of n points can be solved optimally using priority search tree structure