chap15.htm

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

<a name="07fd_1519">15.2-4<a name="07fd_1519"><P>
Let <img src="../images/circx.gif"> be an associative binary operator, and let <I>a</I> be a field maintained in each node of a red-black tree. Suppose that we want to include in each node <I>x</I> an additional field <img src="../images/scrptf12.gif"> such that <img src="../images/scrptf12.gif">[<I>x</I>] = <I>a</I>[<I>x</I><SUB>1</SUB>] <img src="../images/circx.gif"> <I>a</I>[<I>x</I><SUB>2</SUB>], <img src="../images/circx.gif"> <img src="../images/dot10.gif"> <img src="../images/dot10.gif"> <img src="../images/dot10.gif"> <img src="../images/circx.gif"> <I>a</I>[<I>x<SUB>m</I></SUB>], where <I>x</I><SUB>1</SUB>, <I>x</I><SUB>2</SUB>, . . . , <I>x<SUB>m</I></SUB> is the inorder listing of nodes in the subtree rooted at <I>x</I>. Show that the <img src="../images/scrptf12.gif"> fields can be properly updated in <I>O</I>(1) time after a rotation. Modify your argument slightly to show that the<I> size</I> fields in order-statistic trees can be maintained in <I>O</I>(1) time per rotation.<P>
<a name="07fd_151a">15.2-5<a name="07fd_151a"><P>
<a name="07fd_1513"><a name="07fd_1514">We wish to augment red-black trees with an operation RB-<FONT FACE="Courier New" SIZE=2>ENUMERATE</FONT>(<I>x, a,b</I>) that outputs all the keys <I>k</I> such that <I>a&lt; k</I> <img src="../images/lteq12.gif"> <I>b </I>in a red-black tree rooted at<I> x</I>. Describe how RB-<FONT FACE="Courier New" SIZE=2>ENUMERATE</FONT> can be implemented in <img src="../images/bound.gif">(<I>m</I> + lg <I>n</I>) time, where <I>m</I> is the number of keys that are output and <I>n</I> is the number of internal nodes in the tree. (<I>Hint</I>: There is no need to add new fields to the red-black tree.)<P>
<P>


<P>







<h1><a name="07fe_1521">15.3 Interval trees<a name="07fe_1521"></h1><P>
<a name="07fe_1515"><a name="07fe_1516"><a name="07fe_1517"><a name="07fe_1518"><a name="07fe_1519"><a name="07fe_151a">In this section, we shall augment red-black trees to support operations on dynamic sets of intervals. A <I><B>closed interval</I></B> is an ordered pair of real numbers [<I>t</I><SUB>1</SUB>, <I>t</I><SUB>2</SUB>], with <I>t</I><SUB>1</SUB><I> </I><img src="../images/lteq12.gif"><I> t</I><SUB>2</SUB>. The interval [<I>t</I><SUB>1</SUB>, <I>t</I><SUB>2</SUB>] represents the set {<I>t </I><img src="../images/memof12.gif"><I></I> <B>R</B>: <I>t</I><SUB>1</SUB><I> </I><img src="../images/lteq12.gif"><I> t </I><img src="../images/lteq12.gif"><I> t</I><SUB>2</SUB>}. <I><B>Open</I></B> and <I><B>half-open</I></B> intervals omit both or one of the endpoints from the set, respectively. In this section, we shall assume that intervals are closed; extending the results to open and half-open intervals is conceptually straightforward.<P>
<a name="07fe_151b">Intervals are convenient for representing events that each occupy a continuous period of time. We might, for example, wish to query a database of time intervals to find out what events occurred during a given interval. The data structure in this section provides an efficient means for maintaining such an interval database.<P>
<a name="07fe_151c"><a name="07fe_151d"><a name="07fe_151e">We can represent an interval [<I>t</I><SUB>1</SUB>,<I> t</I><SUB>2</SUB>] as an object <I>i, </I>with fields<I> low</I>[<I>i</I>] = <I>t</I><SUB>1 </SUB>(<I>the <B>low endpoint</I></B>)<I> </I>and<I> high</I>[<I>i</I>] = <I>t</I><SUB>2</SUB><I> </I>(<I>the <B>high endpoint</I></B>)<I>. </I>We say that intervals<I> i</I> and <I>i</I>' <I><B>overlap</I></B> if <img src="290_a.gif">, that is, if <I>low</I>[<I>i</I>] <img src="../images/lteq12.gif"> <I>high</I>[<I>i</I><I>'</I>] and <I>low</I>[<I>i</I>'] <img src="../images/lteq12.gif"> <I>high</I>[<I>i</I>]. Any two intervals <I>i</I> and <I>i</I><I>'</I> satisfy the <I><B>interval trichotomy</I></B>; that is, exactly one of the following three properties holds:<P>
a.     <I>i</I> and <I>i</I>' overlap,<P>
b.     <I>high</I>[<I>i</I>] &lt; <I>low</I>[<I>i</I>'],<P>
c.     <I>high</I>[<I>i</I>'] &lt; <I>low</I>[<I>i</I>].<P>
Figure 15.3 shows the three possibilities.<P>
An <I><B>interval tree</I></B> is a red-black tree that maintains a dynamic set of elements, with each element <I>x</I> containing an interval <I>int</I>[<I>x</I>]. Interval trees support the following operations.<P>
<a name="07fe_151f"><FONT FACE="Courier New" SIZE=2>INTERVAL</FONT>-<FONT FACE="Courier New" SIZE=2>INSERT</FONT>(<I>T,x</I>) adds the element <I>x</I>, whose <I>int</I> field is assumed to contain an interval, to the interval tree <I>T</I>.<P>
<img src="290_b.gif"><P>
<h4><a name="07fe_1522">Figure 15.3 The interval trichotomy for two closed intervals i and i'. (a) If i and i'overlap, there are four situations; in each, low[i] <img src="../images/lteq12.gif"> high[i'] and low[i'] <img src="../images/lteq12.gif"> high[i]. (b) high[i] &lt; low[i']. (c) high[i'] &lt; low[i].<a name="07fe_1522"></sub></sup></h4><P>
<img src="291_a.gif"><P>
<h4><a name="07fe_1523">Figure 15.4 An interval tree. (a) A set of 10 intervals, shown sorted bottom to top by left endpoint. (b) The interval tree that represents them. An inorder tree walk of the tree lists the nodes in sorted order by left endpoint.<a name="07fe_1523"></sub></sup></h4><P>
<a name="07fe_1520"><FONT FACE="Courier New" SIZE=2>INTERVAL</FONT>-<FONT FACE="Courier New" SIZE=2>DELETE</FONT>(<I>T,x</I>) removes the element <I>x</I> from the interval tree <I>T</I>.<P>
<FONT FACE="Courier New" SIZE=2>INTERVAL</FONT>-<FONT FACE="Courier New" SIZE=2>SEARCH</FONT>(<I>T,i</I>) returns a pointer to an element <I>x</I> in the interval tree T such that <I>int</I>[<I>x</I>] overlaps interval <I>i</I>, or <FONT FACE="Courier New" SIZE=2>NIL</FONT> if no such element is in the set.<P>
Figure 15.4 shows how an interval tree represents a set of intervals. We shall track the four-step method from Section 15.2 as we review the design of an interval tree and the operations that run on it.<P>





<h2>Step 1:     Underlying data structure</h2><P>
We choose a red-black tree in which each node <I>x</I> contains an interval <I>int</I>[<I>x</I>] and the key of <I>x</I> is the low endpoint, <I>low</I>[<I>int</I>[<I>x</I>]], of the interval. Thus, an inorder tree walk of the data structure lists the intervals in sorted order by low endpoint.<P>
<P>







<h2>Step 2:     Additional information</h2><P>
In addition to the intervals themselves, each node <I>x</I> contains a value <I>max</I>[<I>x</I>], which is the maximum value of any interval endpoint stored in the subtree rooted at <I>x</I>. Since any interval's high endpoint is at least as large as its low endpoint, <I>max</I>[<I>x</I>] is the maximum value of all right endpoints in the subtree rooted at <I>x</I>.<P>
<P>







<h2>Step 3:     Maintaining the information</h2><P>
<a name="0801_1521"><a name="0801_1522">We must verify that insertion and deletion can be performed in <I>O</I>(lg <I>n</I>) time on an interval tree of <I>n</I> nodes. We can determine <I>max</I>[<I>x</I>] given interval <I>int</I>[<I>x</I>] and the <I>max</I> values of node <I>x</I>'s children:<P>
<pre>max[x] = max(high[int[x]], max[left[x]], max[right[x]]).</sub></sup></pre><P>
Thus, by Theorem 15.1, insertion and deletion run in <I>O</I>(lg <I>n</I>) time. In fact, updating the <I>max</I> fields after a rotation can be accomplished in <I>O</I>(1) time, as is shown in Exercises 15.2-4 and 15.3-1.<P>
<P>







<h2>Step 4:     Developing new operations</h2><P>
<a name="0802_1523"><a name="0802_1524">The only new operation we need is <FONT FACE="Courier New" SIZE=2>INTERVAL</FONT>-<FONT FACE="Courier New" SIZE=2>SEARCH</FONT>(<I>T, i</I>), which finds an interval in tree <I>T</I> that overlaps interval <I>i</I>. If there is no interval that overlaps <I>i</I> in the tree, <FONT FACE="Courier New" SIZE=2>NIL</FONT> is returned.<P>
<pre>INTERVAL-SEARCH(<I>T,i</I>)</sub></sup></pre><P>
<pre>1  <I>x</I> <img src="../images/arrlt12.gif"> <I>root</I>[<I>T</I>]</sub></sup></pre><P>
<pre>2  <B>while</B> <I>x </I><img src="../images/noteq.gif"> <I>NIL and </I>i<I> does not overlap </I>int<I>[</I>x<I>]</I></sub></sup></pre><P>
<pre>3      <B>do if</B> <I>left</I>[<I>x</I>]<img src="../images/noteq.gif"><I> NIL and </I>max<I>[</I>left<I>[</I>x<I>]] <img src="../images/gteq.gif"> </I>low<I>[</I>i<I>]</I></sub></sup></pre><P>
<pre>4            <B>then </B><I>x </I><img src="../images/arrlt12.gif"> <I>left</I>[<I>x</I>]</sub></sup></pre><P>
<pre>5            <B>else </B><I>x </I><img src="../images/arrlt12.gif"> <I>right</I>[<I>x</I>]</sub></sup></pre><P>
<pre>6  <B>return </B><I>x</I></sub></sup></pre><P>
The search for an interval that overlaps <I>i</I> starts with <I>x</I> at the root of the tree and proceeds downward. It terminates when either an overlapping interval is found or <I>x</I> becomes <FONT FACE="Courier New" SIZE=2>NIL</FONT>. Since each iteration of the basic loop takes <I>O</I>(1) time, and since the height of an <I>n</I>-node red-black tree is <I>O</I>(lg <I>n</I>), the <FONT FACE="Courier New" SIZE=2>INTERVAL</FONT>-<FONT FACE="Courier New" SIZE=2>SEARCH</FONT> procedure takes <I>O</I>(lg <I>n</I>) time.<P>
Before we see why <FONT FACE="Courier New" SIZE=2>INTERVAL</FONT>-<FONT FACE="Courier New" SIZE=2>SEARCH</FONT> is correct, let's examine how it works on the interval tree in Figure 15.4. Suppose we wish to find an interval that overlaps the interval <I>i</I> = [22, 25]. We begin with <I>x</I> as the root, which contains [16,21] and does not overlap <I>i</I>. Since <I>max</I>[<I>left</I>[<I>x</I>]] = 23 is greater than <I>low</I>[<I>i</I>] = 22, the loop continues with <I>x</I> as the left child of the root--the node containing [8, 9], which also does not overlap <I>i</I>. This time, <I>max</I>[<I>left</I>[<I>x</I>]] = 10 is less than <I>low</I>[<I>i</I>] = 22, so the loop continues with the right child of <I>x </I>as the new<I> x. </I>The interval [15, 23] stored in this node overlaps <I>i</I>, so the procedure returns this node.<P>
As an example of an unsuccessful search, suppose we wish to find an interval that overlaps <I>i</I> = [11, 14] in the interval tree of Figure 15.4. We once again begin with <I>x</I> as the root. Since the root's interval [16, 21] does not overlap <I>i</I>, and since <I>max</I>[<I>left</I>[<I>x</I>]] = 23 is greater than <I>low</I>[<I>i</I>] = 11, we go left to the node containing [8, 9]. (Note that no interval in the right subtree overlaps <I>i</I>--we shall see why later.) Interval [8, 9] does not overlap <I>i</I>, and <I>max</I>[<I>left</I>[<I>x</I>]] = 10 is less than <I>low</I>[<I>i</I>] = 11, so we go right. (Note that no interval in the left subtree overlaps <I>i</I>.) Interval [15, 23] does not overlap <I>i</I>, and its left child is <FONT FACE="Courier New" SIZE=2>NIL</FONT>, so we go right, the loop terminates, and <FONT FACE="Courier New" SIZE=2>NIL</FONT> is returned.<P>
To see why <FONT FACE="Courier New" SIZE=2>INTERVAL</FONT>-<FONT FACE="Courier New" SIZE=2>SEARCH</FONT> is correct, we must understand why it suffices to examine a single path from the root. The basic idea is that at any node <I>x</I>, if <I>int</I>[<I>x</I>] does not overlap <I>i</I>, the search always proceeds in a safe direction: an overlapping interval will definitely be found if there is one in the tree. The following theorem states this property more precisely.<P>
<a name="0802_1525">Theorem 15.2<a name="0802_1525"><P>