chap15.htm

程序设计的艺术,此书是英文版的,经久不衰,非常的经典

Consider any iteration of the <B>while</B> loop during the execution of <FONT FACE="Courier New" SIZE=2>INTERVAL</FONT>-<FONT FACE="Courier New" SIZE=2>SEARCH</FONT>(<I>T, i</I>).<P>
1.     f line 4 is executed (the search goes left), then <I>x</I>'s left subtree contains an interval that overlaps <I>i</I> or no interval in <I>x</I>'s right subtree overlaps <I>i</I>.<P>
2.     If line 5 is executed (the search goes right), then <I>x</I>'s left subtree contains no interval that overlaps <I>i</I>.<P>
<I><B>Proof     </I></B>The proof of both cases depend on the interval trichotomy. We prove case 2 first, since it is simpler. Observe that if line 5 is executed, then because of the branch condition in line 3, we have <I>left</I>[<I>x</I>] = <FONT FACE="Courier New" SIZE=2>NIL</FONT>, or <I>max</I>[<I>left</I>[<I>x</I>]] &lt; <I>low</I>[<I>i</I>]<I>x</I>. If <I>left</I>[<I>x</I>] = <FONT FACE="Courier New" SIZE=2>NIL</FONT>, the subtree rooted at <I>left</I>[<I>x</I>] clearly contains no interval that overlaps <I>i,</I> because it contains no intervals at all. Suppose, therefore, that <I>left</I>[<I>x</I>] <img src="../images/noteq.gif"> <FONT FACE="Courier New" SIZE=2>NIL</FONT> and <I>max</I>[<I>left</I>]<I>x</I>]] &lt; <I>low</I>[<I>i</I>]. Let <I>i</I><I>' </I>be an interval in <I>x</I>'s left subtree. (See Figure 15.5(a).) Since <I>max</I>[<I>left</I>[<I>x</I>]] is the largest endpoint in <I>x</I>'s left subtree, we have<P>
<pre><I>high</I>[<I>i</I>'<I>]  <img src="../images/lteq12.gif">  </I>max<I>[</I>left<I>[</I>x<I>]]</I></sub></sup></pre><P>
<pre>&lt;  <I>low</I>[<I>i</I>] ,</sub></sup></pre><P>
and thus, by the interval trichotomy, <I>i</I><I>'</I> and <I>i</I> do not overlap, which completes the proof of case 2.<P>
To prove case 1, we may assume that no intervals in <I>x</I>'s left subtree overlap <I>i</I> (since if any do, we are done), and thus we need only prove that no intervals in <I>x</I>'s right subtree overlap <I>i</I> under this assumption. Observe that if line 4 is executed, then because of the branch condition in line 3, we have <I>max</I>[<I>left</I>[<I>x</I>]] <img src="../images/gteq.gif"> <I>low</I>[<I>i</I>]. Moreover, by definition of the <I>max</I> field,<P>
<img src="294_a.gif"><P>
<h4><a name="0802_1526">Figure 15.5 Intervals in the proof of Theorem 15.2. The value of max[left[x]] is shown in each case as a dashed line. (a) Case 2: the search goes right. No interval i' can overlap i. (b) Case 1: the search goes left. The left subtree of x contains an interval that overlaps i (situation not shown), or there is an interval i' in x's left subtree such that high[i'] = max[left[x]]. Since i does not overlap i', neither does it overlap any interval i\" in x' s right subtree, since low[i'] <img src="../images/lteq12.gif"> low[i\"].<a name="0802_1526"></sub></sup></h4><P>
there must be some interval <I>i</I><I>'</I> in <I>x</I>'s left subtree such that<P>
<pre>high[i'] = max[left[x]]</sub></sup></pre><P>
<pre><img src="../images/gteq.gif"> low[i].</sub></sup></pre><P>
(Figure 15.5(b) illustrates the situation.) Since <I>i</I> and <I>i</I><I>'</I> do not overlap, and since it is not true that <I>high</I>[<I>i</I><I>'</I>] &lt; <I>low</I>[<I>i</I>], it follows by the interval trichotomy that <I>high</I>[<I>i</I>] &lt; <I>low</I>[<I>i</I><I>'</I>]. Interval trees are keyed on the low endpoints of intervals, and thus the search-tree property implies that for any interval <I>i&quot;</I> in <I>x</I>'s right subtree,<P>
<pre>high[i] &lt; low[i']</sub></sup></pre><P>
<pre><img src="../images/lteq12.gif"> low[i&quot;].</sub></sup></pre><P>
By the interval trichotomy,<I> i</I> and <I>i&quot;</I> do not overlap.      <P>
Theorem 15.2 guarantees that if <FONT FACE="Courier New" SIZE=2>INTERVAL</FONT>-<FONT FACE="Courier New" SIZE=2>SEARCH</FONT> continues with one of <I>x</I>'s children and no overlapping interval is found, a search starting with <I>x</I>'s other child would have been equally fruitless.<P>
<P>







<h2><a name="0803_152d">Exercises<a name="0803_152d"></h2><P>
<a name="0803_152e">15.3-1<a name="0803_152e"><P>
<a name="0803_1525">Write pseudocode for <FONT FACE="Courier New" SIZE=2>LEFT</FONT>-<FONT FACE="Courier New" SIZE=2>ROTATE</FONT> that operates on nodes in an interval tree and updates the <I>max</I> fields in <I>O</I>(1) time.<P>
<a name="0803_152f">15.3-2<a name="0803_152f"><P>
<a name="0803_1526">Rewrite the code for <FONT FACE="Courier New" SIZE=2>INTERVAL</FONT>-<FONT FACE="Courier New" SIZE=2>SEARCH</FONT> so that it works properly when all intervals are assumed to be open.<P>
<a name="0803_1530">15.3-3<a name="0803_1530"><P>
<a name="0803_1527"><a name="0803_1528">Describe an efficient algorithm that, given an interval <I>i,</I> returns an interval overlapping <I>i</I> that has the minimum low endpoint, or <FONT FACE="Courier New" SIZE=2>NIL</FONT> if no such interval exists.<P>
<a name="0803_1531">15.3-4<a name="0803_1531"><P>
Given an interval tree <I>T</I> and an interval <I>i,</I> describe how all intervals in <I>T </I>that overlap <I>i</I> can be listed in <I>O</I>(min(<I>n, k</I> 1g <I>n</I>)) time, where <I>k</I> is the number of intervals in the output list. (<I>Optional:</I> Find a solution that does not modify the tree.)<P>
<a name="0803_1532">15.3-5<a name="0803_1532"><P>
<a name="0803_1529"><a name="0803_152a">Suggest modifications to the interval-tree procedures to support the operation <FONT FACE="Courier New" SIZE=2>INTERVAL</FONT>-<FONT FACE="Courier New" SIZE=2>SEARCH</FONT>-<FONT FACE="Courier New" SIZE=2>EXACTLY</FONT>(<I>T, i</I>), which returns a pointer to a node <I>x </I>in interval tree <I>T </I>such that <I>low</I>[<I>int</I>]<I>x</I>]] = <I>low</I>[<I>i</I>] and <I>high</I>[<I>int</I>[<I>x</I>]] = <I>high</I>[<I>i</I>], or <FONT FACE="Courier New" SIZE=2>NIL</FONT> if <I>T </I>contains no such node. All operations, including <FONT FACE="Courier New" SIZE=2>INTERVAL</FONT>-<FONT FACE="Courier New" SIZE=2>SEARCH</FONT>-<FONT FACE="Courier New" SIZE=2>EXACTLY</FONT>, should run in <I>O</I>(1g <I>n</I>) time on an <I>n</I>-node tree.<P>
<a name="0803_1533">15.3-6<a name="0803_1533"><P>
<a name="0803_152b">Show how to maintain a dynamic set <I>Q</I> of numbers that supports the operation <FONT FACE="Courier New" SIZE=2>MIN</FONT>-<FONT FACE="Courier New" SIZE=2>GAP</FONT>, which gives the magnitude of the difference of the two closest numbers in <I>Q.</I> For example, if <I>Q</I> = {1, 5, 9, 15, 18, 22}, then <FONT FACE="Courier New" SIZE=2>MIN</FONT>-<FONT FACE="Courier New" SIZE=2>GAP</FONT>(<I>Q</I>) returns 18 - 15 = 3, since 15 and 18 are the two closest numbers in <I>Q</I>. Make the operations <FONT FACE="Courier New" SIZE=2>INSERT</FONT>, <FONT FACE="Courier New" SIZE=2>DELETE</FONT>, <FONT FACE="Courier New" SIZE=2>SEARCH</FONT>, and <FONT FACE="Courier New" SIZE=2>MIN</FONT>-<FONT FACE="Courier New" SIZE=2>GAP</FONT> as efficient as possible, and analyze their running times.<P>
<a name="0803_1534">15.3-7<a name="0803_1534"><P>
<a name="0803_152c">VLSI databases commonly represent an integrated circuit as a list of rectangles. Assume that each rectangle is rectilinearly oriented (sides parallel to the <I>x</I>- and <I>y</I>-axis), so that a representation of a rectangle consists of its minimum and maximum <I>x</I>- and <I>y</I>-coordinates. Give an <I>O</I>(<I>n</I> 1g <I>n</I>)-time algorithm to decide whether or not a set of rectangles so represented contains two rectangles that overlap. Your algorithm need not report all intersecting pairs, but it must report that an overlap exists if one rectangle entirely covers another, even if the boundary lines do not intersect. (<I>Hint:</I> Move a &quot;sweep&quot; line across the set of rectangles.)<P>
<P>


<P>







<h1><a name="0804_152f">Problems<a name="0804_152f"></h1><P>
<a name="0804_1530">15-1     Point of maximum overlap<a name="0804_1530"><P>
Suppose that we wish to keep track of a <I><B>point of maximum overlap</I></B> in a set of intervals--a point that has the largest number of intervals in the database overlapping it. Show how the point of maximum overlap can be maintained efficiently while intervals are inserted and deleted.<P>
<a name="0804_1531">15-2     Josephus permutation<a name="0804_1531"><P>
<a name="0804_152d"><a name="0804_152e">The <I><B>Josephus problem</I></B> is defined as follows. Suppose that <I>n</I> people are arranged in a circle and that we are given a positive integer <I>m</I> <img src="../images/lteq12.gif"> <I>n</I>. Beginning with a designated first person, we proceed around the circle, removing every <I>m</I>th person. After each person is removed, counting continues around the circle that remains. This process continues until all <I>n</I> people have been removed. The order in which the people are removed from the circle defines the (<I><B>n, m)-Josephus permutation </I></B>of the integers 1, 2, . . . , n. For example, the (7, 3)-Josephus permutation is &lt; 3, 6, 2, 7, 5, 1, 4 &gt; .<P>
<I><B>a.     </I></B>Suppose that <I>m</I> is a constant. Describe an <I>O</I>(<I>n</I>)-time algorithm that, given an integer <I>n</I>, outputs the (<I>n, m</I>)-Josephus permutation.<P>
<I><B>b.     </I></B>Suppose that <I>m</I> is not a constant. Describe an <I>O</I>(<I>n</I> 1g <I>n</I>)-time algorithm that, given integers <I>n</I> and <I>m</I>, outputs the (<I>n</I>, <I>m</I>)-Josephus permutation.<P>
<P>







<h1>Chapter notes</h1><P>
Preparata and Shamos [160] describe several of the interval trees that appear in the literature. Among the more important theoretically are those due independently to H. Edelsbrunner (1980) and E. M. McCreight (1981), which, in a database of <I>n</I> intervals, allow all <I>k</I> intervals that overlap a given query interval to be enumerated in <I>O</I>(<I>k</I> + 1g <I>n</I>) time.<P>
<P>


<P>
<P>
<center>Go to <a href="partiv.htm">Part IV</A>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Back to <a href="toc.htm">Table of Contents</A>
</P>
</center>


</BODY></HTML>