Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 58
Текст из файла (страница 58)
It terminates when either an overlapping interval is found or x points to thesentinel nil[T]. Since each iteration of the basic loop takes O(1) time, and since the height ofan n-node red-black tree is O(lg n), the INTERVAL-SEARCH procedure takes O(lg n) time.Before we see why INTERVAL-SEARCH is correct, let's examine how it works on theinterval tree in Figure 14.4. Suppose we wish to find an interval that overlaps the interval i =[22, 25].
We begin with x as the root, which contains [16, 21] and does not overlap i. Sincemax[left[x]] = 23 is greater than low[i] = 22, the loop continues with x as the left child of theroot—the node containing [8, 9], which also does not overlap i. This time, max[left[x]] = 10 isless than low[i] = 22, so the loop continues with the right child of x as the new x.
The interval[15, 23] stored in this node overlaps i, so the procedure returns this node.As an example of an unsuccessful search, suppose we wish to find an interval that overlaps i =[11, 14] in the interval tree of Figure 14.4. We once again begin with x as the root. Since theroot's interval [16, 21] does not overlap i, and since max[left[x]] = 23 is greater than low[i] =11, we go left to the node containing [8, 9]. (Note that no interval in the right subtree overlapsi—we shall see why later.) Interval [8, 9] does not overlap i, and max[left[x]] = 10 is less thanlow[i] = 11, so we go right. (Note that no interval in the left subtree overlaps i.) Interval [15,23] does not overlap i, and its left child is nil[T], so we go right, the loop terminates, and thesentinel nil[T] is returned.To see why INTERVAL-SEARCH is correct, we must understand why it suffices to examinea single path from the root.
The basic idea is that at any node x, if int[x] does not overlap i, thesearch always proceeds in a safe direction: an overlapping interval will definitely be found ifthere is one in the tree. The following theorem states this property more precisely.Theorem 14.2Any execution of INTERVAL-SEARCH(T, i) either returns a node whose interval overlaps i,or it returns nil[T] and the tree T contains no node whose interval overlaps i.Proof The while loop of lines 2–5 terminates either when x = nil[T] or i overlaps int[x].
In thelatter case, it is certainly correct to return x. Therefore, we focus on the former case, in whichthe while loop terminates because x = nil[T].We use the following invariant for the while loop of lines 2–5:•If tree T contains an interval that overlaps i, then there is such an interval in thesubtree rooted at x.We use this loop invariant as follows:••Initialization: Prior to the first iteration, line 1 sets x to be the root of T , so that theinvariant holds.Maintenance: In each iteration of the while loop, either line 4 or line 5 is executed.We shall show that the loop invariant is maintained in either case.If line 5 is executed, then because of the branch condition in line 3, we have left[x] =nil[T], or max[left[x]]< low[i]. If left[x] = nil[T], the subtree rooted at left[x] clearlycontains no interval that overlaps i, and so setting x to right[x] maintains the invariant.Suppose, therefore, that left[x] ≠ nil[T] and max[left[x]]< low[i].
As Figure 14.5(a)shows, for each interval i' in x's left subtree, we havehigh[i'] ≤ max[left[x]]< low[i].Figure 14.5: Intervals in the proof of Theorem 14.2. The value of max[left[x]] is shownin each case as a dashed line. (a) The search goes right. No interval i' in x's left subtreecan overlap i. (b) The search goes left. The left subtree of x contains an interval thatoverlaps i (situation not shown), or there is an interval i' in x's left subtree such thathigh[i'] = max[left[x]].
Since i does not overlap i', neither does it overlap any intervali" in x's right subtree, since low[i'] ≤ low[i"].By the interval trichotomy, therefore, i' and i do not overlap. Thus, the left subtree of xcontains no intervals that overlap i, so that setting x to right[x] maintains the invariant.If, on the other hand, line 4 is executed, then we will show that the contrapositive ofthe loop invariant holds. That is, if there is no interval overlapping i in the subtreerooted at left[x], then there is no interval overlapping i anywhere in the tree. Since line4 is executed, then because of the branch condition in line 3, we have max[left[x]] ≥low[i].
Moreover, by definition of the max field, there must be some interval i' in x'sleft subtree such thathigh[i'] = max[left[x]]≥ low[i].(Figure 14.5(b) illustrates the situation.) Since i and i' do not overlap, and since it isnot true that high[i']< low[i], it follows by the interval trichotomy that high[i]< low[i'].Interval trees are keyed on the low endpoints of intervals, and thus the search-treeproperty implies that for any interval i" in x's right subtree,high[i] < low[i']≤ low[i"].By the interval trichotomy, i and i" do not overlap. We conclude that whether or notany interval in x's left subtree overlaps i, setting x to left[x] maintains the invariant.•Termination: If the loop terminates when x = nil[T], there is no interval overlapping iin the subtree rooted at x.
The contrapositive of the loop invariant implies that Tcontains no interval that overlaps i. Hence it is correct to return x = nil[T].Thus, the INTERVAL-SEARCH procedure works correctly.Exercises 14.3-1Write pseudocode for LEFT-ROTATE that operates on nodes in an interval tree and updatesthe max fields in O(1) time.Exercises 14.3-2Rewrite the code for INTERVAL-SEARCH so that it works properly when all intervals areassumed to be open.Exercises 14.3-3Describe an efficient algorithm that, given an interval i, returns an interval overlapping i thathas the minimum low endpoint, or nil[T] if no such interval exists.Exercises 14.3-4Given an interval tree T and an interval i, describe how all intervals in T that overlap i can belisted in O(min(n, k lg n)) time, where k is the number of intervals in the output list.(Optional: Find a solution that does not modify the tree.)Exercises 14.3-5Suggest modifications to the interval-tree procedures to support the new operationINTERVAL-SEARCH-EXACTLY(T, i), which returns a pointer to a node x in interval tree Tsuch that low[int[x]] = low[i] and high[int[x]] = high[i], or nil[T] if T contains no such node.All operations, including INTERVAL-SEARCH-EXACTLY, should run in O(lg n) time onan n-node tree.Exercises 14.3-6Show how to maintain a dynamic set Q of numbers that supports the operation MIN-GAP,which gives the magnitude of the difference of the two closest numbers in Q.
For example, ifQ = {1, 5, 9, 15, 18, 22}, then MIN-GAP(Q) returns 18 - 15 = 3, since 15 and 18 are the twoclosest numbers in Q. Make the operations INSERT, DELETE, SEARCH, and MIN-GAP asefficient as possible, and analyze their running times.Exercises 14.3-7: ⋆VLSI databases commonly represent an integrated circuit as a list of rectangles. Assume thateach rectangle is rectilinearly oriented (sides parallel to the x- and y-axis), so that arepresentation of a rectangle consists of its minimum and maximum x- and y-coordinates.Give an O(n lg n)-time algorithm to decide whether or not a set of rectangles so representedcontains two rectangles that overlap.
Your algorithm need not report all intersecting pairs, butit must report that an overlap exists if one rectangle entirely covers another, even if theboundary lines do not intersect. (Hint: Move a "sweep" line across the set of rectangles.)Problems 14-1: Point of Maximum OverlapSuppose that we wish to keep track of a point of maximum overlap in a set of intervals—apoint that has the largest number of intervals in the database overlapping it.a. Show that there will always be a point of maximum overlap which is an endpoint ofone of the segments.b. Design a data structure that efficiently supports the operations INTERVAL-INSERT,INTERVAL-DELETE, and FIND-POM, which returns a point of maximum overlap.(Hint: Keep a red-black tree of all the endpoints.
Associate a value of +1 with eachleft endpoint, and associate a value of -1 with each right endpoint. Augment each nodeof the tree with some extra information to maintain the point of maximum overlap.)Problems 14-2: Josephus PermutationThe Josephus problem is defined as follows. Suppose that n people are arranged in a circleand that we are given a positive integer m ≤ n. Beginning with a designated first person, weproceed around the circle, removing every mth person. After each person is removed,counting continues around the circle that remains.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
