chap13.htm

美国麻省理工的算法导论,英文版,看后程序员宏观的能力培养有好处

<a name="07e2_14a1"><a name="07e2_14a2">The procedure for deleting a given node <I>z</I> from a binary search tree takes as an argument a pointer to <I>z</I>. The procedure considers the three cases shown in Figure 13.4. If <I>z</I> has no children, we modify its parent <I>p</I>[<I>z</I>] to replace <I>z</I> with <FONT FACE="Courier New" SIZE=2>NIL</FONT> as its child. If the node has only a single child, we "splice out" <I>z</I> by making a new link between its child and its parent. Finally, if the node has two children, we splice out <I>z</I>'s successor <I>y</I>, which has no left child (see Exercise 13.3-4) and replace the contents of <I>z</I> with the contents of <I>y</I>.<P>
The code for <FONT FACE="Courier New" SIZE=2>TREE</FONT>-<FONT FACE="Courier New" SIZE=2>DELETE</FONT> organizes these three cases a little differently.<P>
<img src="252_a.gif"><P>
<h4><a name="07e2_14a4">Figure 13.3 Inserting an item with key 13 into a binary search tree. Lightly shaded nodes indicate the path from the root down to the position where the item is inserted. The dashed line indicates the link in the tree that is added to insert the item.<a name="07e2_14a4"></sub></sup></h4><P>
<img src="252_b.gif"><P>
<h4><a name="07e2_14a5">Figure 13.4 Deleting a node z from a binary search tree. In each case, the node actually removed is lightly shaded. (a) If z has no children, we just remove it. (b) If z has only one child, we splice out z. (c) If z has two children, we splice out its successor y, which has at most one child, and then replace the contents of z with the contents of y.<a name="07e2_14a5"></sub></sup></h4><P>
<pre><a name="07e2_14a3">TREE-DELETE(<I>T, z</I>)</sub></sup></pre><P>
<pre>1  <B>if</B> <I>left</I>[<I>z</I>] = NIL or <I>right</I>[<I>z</I>] = NIL</sub></sup></pre><P>
<pre>2      <B>then</B> <I>y</I> <img src="../images/arrlt12.gif"> <I>z</I></sub></sup></pre><P>
<pre>3      <B>else</B> <I>y</I> <img src="../images/arrlt12.gif"> TREE-SUCCESSOR(<I>z</I>)</sub></sup></pre><P>
<pre>4  <B>if</B> <I>left</I>[<I>y</I>] <img src="../images/noteq.gif"> NIL</sub></sup></pre><P>
<pre>5      <B>then</B> <I>x</I> <img src="../images/arrlt12.gif"> <I>left</I>[<I>y</I>]</sub></sup></pre><P>
<pre>6      <B>else</B> <I>x</I> <img src="../images/arrlt12.gif"> <I>right</I>[<I>y</I>]</sub></sup></pre><P>
<pre>7  <B>if</B> <I>x</I> <img src="../images/noteq.gif"> NIL</sub></sup></pre><P>
<pre>8      <B>then</B> <I>p</I>[<I>x</I>] <img src="../images/arrlt12.gif"> <I>p</I>[<I>y</I>]</sub></sup></pre><P>
<pre>9  <B>if</B> <I>p</I>[<I>y</I>] = NIL</sub></sup></pre><P>
<pre>10      <B>then</B> <I>root</I>[<I>T</I>] <img src="../images/arrlt12.gif"> <I>x</I></sub></sup></pre><P>
<pre>11      <B>else if</B> <I>y</I> = <I>left</I>[<I>p</I>[<I>y</I>]]</sub></sup></pre><P>
<pre>12              <B>then</B> <I>left</I>[<I>p</I>[<I>y</I>]] <img src="../images/arrlt12.gif"> <I>x</I></sub></sup></pre><P>
<pre>13              <B>else</B> <I>right</I>[<I>p</I>[<I>y</I>]] <img src="../images/arrlt12.gif"> <I>x</I></sub></sup></pre><P>
<pre>14  <B>if</B> <I>y</I> <img src="../images/noteq.gif"> <I>z</I></sub></sup></pre><P>
<pre>15      <B>then</B> <I>key</I>[<I>z</I>] <img src="../images/arrlt12.gif"> <I>key</I>[<I>y</I>]</sub></sup></pre><P>
<pre>16           <img src="253_a.gif"> If <I>y</I> has other fields, copy them, too.</sub></sup></pre><P>
<pre>17  <B>return</B> <I>y</I></sub></sup></pre><P>
In lines 1-3, the algorithm determines a node <I>y</I> to splice out. The node <I>y</I> is either the input node <I>z</I> (if <I>z</I> has at most 1 child) or the successor of <I>z</I> (if <I>z</I> has two children). Then, in lines 4-6, <I>x</I> is set to the non-<FONT FACE="Courier New" SIZE=2>NIL</FONT> child of <I>y</I>, or to <FONT FACE="Courier New" SIZE=2>NIL</FONT> if <I>y</I> has no children. The node <I>y</I> is spliced out in lines 7-13 by modifying pointers in <I>p</I>[<I>y</I>] and <I>x</I>. Splicing out <I>y</I> is somewhat complicated by the need for proper handling of the boundary conditions, which occur when <I>x</I> = <FONT FACE="Courier New" SIZE=2>NIL</FONT> or when <I>y</I> is the root. Finally, in lines 14-16, if the successor of <I>z</I> was the node spliced out, the contents of <I>z</I> are moved from <I>y</I> to <I>z</I>, overwriting the previous contents. The node <I>y</I> is returned in line 17 so that the calling procedure can recycle it via the free list. The procedure runs in <I>O</I>(<I>h</I>) time on a tree of height <I>h</I>.<P>
In summary, we have proved the following theorem.<P>
<a name="07e2_14a6">Theorem 13.2<a name="07e2_14a6"><P>
The dynamic-set operations <FONT FACE="Courier New" SIZE=2>INSERT</FONT> and <FONT FACE="Courier New" SIZE=2>DELETE</FONT> can be made to run in <I>O</I>(<I>h</I>) time on a binary search tree of height <I>h.     </I> <P>
<P>









<h2><a name="07e3_14a7">Exercises<a name="07e3_14a7"></h2><P>
<a name="07e3_14a8">13.3-1<a name="07e3_14a8"><P>
<a name="07e3_14a4">Give a recursive version of the <FONT FACE="Courier New" SIZE=2>TREE</FONT>-<FONT FACE="Courier New" SIZE=2>INSERT</FONT> procedure.<P>
<a name="07e3_14a9">13.3-2<a name="07e3_14a9"><P>
Suppose that a binary search tree is constructed by repeatedly inserting distinct values into the tree. Argue that the number of nodes examined in searching for a value in the tree is one plus the number of nodes examined when the value was first inserted into the tree.<P>
<a name="07e3_14aa">13.3-3<a name="07e3_14aa"><P>
<a name="07e3_14a5"><a name="07e3_14a6">We can sort a given set of <I>n</I> numbers by first building a binary search tree containing these numbers (using <FONT FACE="Courier New" SIZE=2>TREE</FONT>-<FONT FACE="Courier New" SIZE=2>INSERT</FONT> repeatedly to insert the numbers one by one) and then printing the numbers by an inorder tree walk. What are the worst-case and best-case running times for this sorting algorithm?<P>
<a name="07e3_14ab">13.3-4<a name="07e3_14ab"><P>
Show that if a node in a binary search tree has two children, then its successor has no left child and its predecessor has no right child.<P>
<a name="07e3_14ac">13.3-5<a name="07e3_14ac"><P>
Suppose that another data structure contains a pointer to a node <I>y</I> in a binary search tree, and suppose that <I>y</I>'s predecessor <I>z</I> is deleted from the tree by the procedure <FONT FACE="Courier New" SIZE=2>TREE</FONT>-<FONT FACE="Courier New" SIZE=2>DELETE</FONT>. What problem can arise? How can <FONT FACE="Courier New" SIZE=2>TREE</FONT>-<FONT FACE="Courier New" SIZE=2>DELETE</FONT> be rewritten to solve this problem?<P>
<a name="07e3_14ad">13.3-6<a name="07e3_14ad"><P>
Is the operation of deletion "commutative" in the sense that deleting <I>x</I> and then <I>y</I> from a binary search tree leaves the same tree as deleting <I>y</I> and then <I>x</I>? Argue why it is or give a counterexample.<P>
<a name="07e3_14ae">13.3-7<a name="07e3_14ae"><P>
When node <I>z</I> in <FONT FACE="Courier New" SIZE=2>TREE</FONT>-<FONT FACE="Courier New" SIZE=2>DELETE</FONT> has two children, we could splice out its predecessor rather than its successor. Some have argued that a fair strategy, giving equal priority to predecessor and successor, yields better empirical performance. How might <FONT FACE="Courier New" SIZE=2>TREE</FONT>-<FONT FACE="Courier New" SIZE=2>DELETE</FONT> be changed to implement such a fair strategy?<P>
<P>


<P>









<h1><a name="07e4_14ac">* 13.4 Randomly built binary search trees<a name="07e4_14ac"></h1><P>
<a name="07e4_14a7">We have shown that all the basic operations on a binary search tree run in <I>O</I>(<I>h</I>) time, where <I>h</I> is the height of the tree. The height of a binary search tree varies, however, as items are inserted and deleted. In order to analyze the behavior of binary search trees in practice, it is reasonable to make statistical assumptions about the distribution of keys and the sequence of insertions and deletions.<P>
<a name="07e4_14a8"><a name="07e4_14a9">Unfortunately, little is known about the average height of a binary search tree when both insertion and deletion are used to create it. When the tree is created by insertion alone, the analysis becomes more tractable. Let us therefore define a <I><B>randomly built binary search tree</I></B> on <I>n</I> distinct keys as one that arises from inserting the keys in random order into an initially empty tree, where each of the <I>n</I>! permutations of the input keys is equally likely. (Exercise 13.4-2 asks you to show that this notion is different from assuming that every binary search tree on <I>n</I> keys is equally likely.) The goal of this section is to show that the expected height of a randomly built binary search tree on <I>n</I> keys is <I>O</I>(lg <I>n</I>).<P>
We begin by investigating the structure of binary search trees that are built by insertion alone.<P>
<a name="07e4_14ad">Lemma 13.3<a name="07e4_14ad"><P>
Let <I>T</I> be the tree that results from inserting <I>n</I> distinct keys <I>k</I><SUB>1</SUB>,<I> k</I><SUB>2</SUB>, . . . ,<I> k<SUB>n</I></SUB> (in order) into an initially empty binary search tree. Then <I>k<SUB>i</I></SUB> is an ancestor of <I>k<SUB>j</I></SUB> in <I>T</I>, for l <img src="../images/lteq12.gif"> <I>i</I> &lt; <I>j</I> <img src="../images/lteq12.gif"> <I>n</I>, if and only if<P>
<pre><I>k<SUB>i</I></SUB> = min {<I>k<SUB>l</I></SUB> : 1 <img src="../images/lteq12.gif"> <I>l</I> <img src="../images/lteq12.gif"> <I>i</I> and <I>k<SUB>l</I></SUB> &gt; <I>k<SUB>j</I></SUB>}</sub></sup></pre><P>
or<P>
<pre><I>k<SUB>i</I></SUB> = max {<I>k<SUB>l</I></SUB>: 1 <img src="../images/lteq12.gif"> <I>l</I> <img src="../images/lteq12.gif"> <I>i</I> and <I>k<SUB>l</I></SUB> &lt; <I>k<SUB>j</I></SUB>} .</sub></sup></pre><P>
<I><B>Proof     </I></B><img src="../images/rtbigar.gif">: Suppose that <I>k<SUB>i</I></SUB> is an ancestor of <I>k<SUB>j</I></SUB>. Consider the tree <I>T<SUB>i</I></SUB> that results after the keys <I>k</I><SUB>1</SUB>, <I>k</I><SUB>2</SUB>, . . . , <I>k<SUB>i</I></SUB> have been inserted. The path in <I>T<SUB>i </I></SUB>from the root to <I>k<SUB>i</I></SUB> is the same as the path in <I>T</I> from the root to <I>k<SUB>i</I></SUB>. Thus, if <I>k<SUB>j</I></SUB> were inserted into <I>T<SUB>i</I></SUB>, it would become either the left or the right child of <I>k<SUB>i</I></SUB>. Consequently (see Exercise 13.2-6), <I>k<SUB>i</I></SUB> is either the smallest key among <I>k</I><SUB>1</SUB>, <I>k</I><SUB>2</SUB>, . . . , <I>k<SUB>i</I></SUB> that is larger than <I>k<SUB>j</I></SUB> or the largest key among <I>k</I><SUB>1</SUB>, <I>k</I><SUB>2</SUB>, . . . , <I>k<SUB>i</I></SUB> that is smaller than <I>k<SUB>j</I></SUB>.<P>
<img src="../images/lftbigar.gif">: Suppose that <I>k<SUB>i</I></SUB> is the smallest key among <I>k</I><SUB>1</SUB>, <I>k</I><SUB>2</SUB>, . . . , <I>k<SUB>i</I></SUB> that is larger than <I>k<SUB>j</I></SUB>. (The case in which <I>k<SUB>i</I></SUB> is the largest key among <I>k</I><SUB>1</SUB>,<SUB> </SUB><I>k</I><SUB>2</SUB>, . . . , <I>k<SUB>i</I></SUB> that is smaller than <I>k<SUB>j</I></SUB> is handled symmetrically.) Comparing <I>k<SUB>j</I></SUB> to any of the keys on the path in <I>T</I> from the root to <I>k<SUB>i</I></SUB> yields the same results as comparing <I>k<SUB>i</I></SUB> to the keys. Hence, when <I>k<SUB>j</I></SUB> is inserted, it follows a path through <I>k<SUB>i</I></SUB> and is inserted as a descendant of <I>k<SUB>i</I></SUB>.      <P>
As a corollary of Lemma 13.3, we can precisely characterize the depth of a key based on the input permutation.<P>
<a name="07e4_14ae">Corollary 13.4<a name="07e4_14ae"><P>
Let <I>T</I> be the tree that results from inserting <I>n</I> distinct keys <I>k</I><SUB>1</SUB>, <I>k</I><SUB>2</SUB>, . . . , <I>k<SUB>n</I></SUB> (in order) into an initially empty binary search tree. For a given key <I>k<SUB>j</I></SUB>, where 1 <img src="../images/lteq12.gif"> <I>j</I> <img src="../images/lteq12.gif"> <I>n</I>, define<P>
<pre><I>G<SUB>j</I></SUB> = {<I>k<SUB>i</I></SUB> : 1 <img src="../images/lteq12.gif"> <I>i</I> &lt; <I>j</I> and <I>k<SUB>l</I></SUB> &gt; <I>k<SUB>i</I></SUB> &gt; <I>k<SUB>j</I></SUB> for all <I>l</I> &lt; <I>i</I> such that <I>k<SUB>l</I></SUB> &gt; <I>k<SUB>j</I></SUB>}</sub></sup></pre><P>
and<P>
<pre><I>L<SUB>j</I></SUB> = {<I>k<SUB>i</I></SUB> : 1 <img src="../images/lteq12.gif"> <I>i</I> &lt; <I>j</I> and <I>k<SUB>l</I></SUB> &lt; <I>k<SUB>i</I></SUB> &lt; <I>k<SUB>j</I></SUB> for all <I>l</I> &lt; <I>i</I> such that <I>k<SUB>l</I></SUB> &lt; <I>k<SUB>j</I></SUB>} .</sub></sup></pre><P>
Then the keys on the path from the root to <I>k<SUB>j</I></SUB> are exactly the keys in <I>G<SUB>j</I></SUB> <FONT FACE="Times New Roman" SIZE=3><img src="../images/wideu.gif"></FONT> <I>L<SUB>j</I></SUB>, and the depth in <I>T</I> of any key <I>k<SUB>j</I></SUB> is<P>
<pre><I>d</I>(<I>k<SUB>j</I></SUB>, <I>T</I>) = |<I>G<SUB>j</SUB>| + |</I>L<SUB>j<I></SUB>| .                                                    </I></sub></sup></pre><P>
Figure 13.5 illustrates the two sets <I>G<SUB>j</I></SUB> and <I>L<SUB>j</I></SUB>. The set <I>G<SUB>j</I></SUB> contains any key <I>k<SUB>i</I></SUB> inserted before <I>k<SUB>j</I></SUB> such that <I>k<SUB>i</I></SUB> is the smallest key among <I>k</I><SUB>1</SUB>, <I>k</I><SUB>2</SUB>, . . . , <I>k<SUB>i</I></SUB> that is larger than <I>k<SUB>j</I></SUB>. (The structure of <I>L<SUB>j</I></SUB> is symmetric.) To better understand the set <I>G<SUB>j</I></SUB>, let us explore a method by which we can enumerate its elements. Among the keys <I>k</I><SUB>1</SUB>, <I>k</I><SUB>2</SUB>, . . . , <I>k<SUB>j</I></SUB>-<SUB>1</SUB>, consider in order those that are larger than <I>k<SUB>j</I></SUB>. These keys are shown as <I>G</I>'<I><SUB>j</I></SUB>, in the figure. As each key is considered in turn, keep a running account of the minimum. The set <I>G<SUB>j</I></SUB> consists of those elements that update the running minimum.<P>
Let us simplify this scenario somewhat for the purpose of analysis. Suppose that <I>n</I> distinct numbers are inserted one at a time into a dynamic set. If all permutations of the numbers are equally likely, how many times on average does the minimum of the set change? To answer this question, suppose that the <I>i</I>th number inserted is <I>k<SUB>i</I></SUB>, for <I>i</I> = 1, 2, . . . , <I>n</I>. The probability is l/<I>i</I> that <I>k<SUB>i</I></SUB> is the minimum of the first <I>i</I> numbers, since the rank of <I>k<SUB>i</I></SUB> among the first <I>i</I> numbers is equally likely to be any of the <I>i</I> possible ranks. Consequently, the expected number of changes to the minimum of the set is<P>
<img src="256_a.gif"><P>
where <I>H<SUB>n</I></SUB> = ln <I>n</I> + <I>O</I>(1) is the <I>n</I>th harmonic number (see equation (3.5) and Problem 6-2).<P>
We therefore expect the number of changes to the minimum to be approximately ln <I>n</I>, and the following lemma shows that the probability that it is much greater is very small.<P>
<a name="07e4_14af">Lemma 13.5<a name="07e4_14af"><P>
Let <I>k</I><SUB>1</SUB>, <I>k</I><SUB>2</SUB>, . . . , <I>k<SUB>n</I></SUB> be a random permutation of <I>n</I> distinct numbers, and let |<I>S</I>| be the random variable that is the cardinality of the set<P>
<pre><I>S</I> = {<I>k<SUB>i</I></SUB> : 1 <img src="../images/lteq12.gif"> <I>i</I> <img src="../images/lteq12.gif"> <I>n</I> and <I>k<SUB>l</I></SUB> &gt; <I>k<SUB>i</SUB> </I>for all <I>l</I> &lt; <I>i</I>} .</sub></sup></pre><P>
<h4><a name="07e4_14b0">(13.1)<a name="07e4_14b0"></sub></sup></h4><P>
Then Pr{|<I>S</I>| <img src="../images/gteq.gif"> (<img src="../images/beta14.gif"><I> + 1)</I>H<SUB>n<I></SUB>} <img src="../images/lteq12.gif"> 1/</I>n<I><SUP>2</SUP>, where </I>H<SUB>n<I></SUB> is the </I>n<I>th harmonic number and <img src="../images/beta14.gif"></I> <img src="../images/approx18.gif"> 4.32 satisfies the equation (ln <img src="../images/beta14.gif"><I> - 1) <img src="../images/beta14.gif"></I> = 2.<P>
<a name="07e4_14aa"><I><B>Proof     </I></B>We can view the cardinality of the set <I>S</I> as being determined by <I>n</I> Bernoulli trials, where a success occurs in the <I>i</I>th trial when <I>k<SUB>i</I></SUB> is smaller than the elements <I>k</I><SUB>1</SUB>, <I>k</I><SUB>2</SUB>, . . . , <I>k<SUB>i</I></SUB>-<SUB>l</SUB>. Success in the <I>i</I>th trial occurs with probability 1/<I>i</I>. The trials are independent, since the probability that <I>k<SUB>i</I></SUB> is the minimum of <I>k</I><SUB>1</SUB>, <I>k</I><SUB>2</SUB>, . . . , <I>k<SUB>i</I></SUB> is independent of the relative ordering of <I>k</I><SUB>1</SUB>, <I>k</I><SUB>2</SUB>, . . . , <I>k<SUB>i</I></SUB>-<SUB>1</SUB>.<P>
We can use Theorem 6.6 to bound the probability that |<I>S</I>| <img src="../images/gteq.gif"> (<img src="../images/beta14.gif"><I></I> + 1 )<I>H<SUB>n</I></SUB> . The expectation of |<I>S</I>| is <img src="../images/mu12.gif"><I></I> = <I>H<SUB>n</I></SUB> <img src="../images/gteq.gif"> ln <I>n</I>. Since <img src="../images/beta14.gif"><I></I> &gt; 1, Theorem 6.6 yields<P>
<img src="257_a.gif"><P>
<h4><a name="07e4_14b1">Figure 13.5 Illustrating the two sets G<SUB>j</SUB> and L<SUB>j </SUB>that comprise the keys on a path from the root of a binary search tree to a key k<SUB>j = </SUB>17. (a) The nodes with keys in G<sub>j</sub> are black, and the nodes with keys in L<SUB>j</SUB> are white. All other nodes are shaded. The path from the root down to the node with key k<SUB>j</SUB> is shaded. Keys to the left of the dashed line are less than k<SUB>j</SUB>, and keys to the right are greater. The tree is constructed by inserting the keys shown in the topmost list in (b). The set G'<SUB>j</SUB> = {21, 25, 19, 29}consists of those elements that are inserted before 17 and are greater than 17. The set G<SUB>j</SUB> = {21, 19} consists of those elements that update a running minimum of the elements in G'<SUB>j</SUB>. Thus, the key 21 is in G<SUB>j</SUB>, since it is the first element. The key 25 is not in G<SUB>j</SUB>, since it is larger than the running minimum 21. The key 19 is in G<SUB>j,</SUB> since it is smaller than the running minimum 21. The key 29 is not in G<SUB>j</SUB>, since it is larger than the running minimum 19. The structures of L'<SUB>j</SUB> and L<SUB>j</SUB> are symmetric.<a name="07e4_14b1"></sub></sup></h4><P>
<img src="258_a.gif"><P>
which follows from the definition of <img src="../images/beta14.gif"><I>.      </I><P>
<a name="07e4_14ab">We now have the tools to bound the height of a randomly built binary search tree.<P>
<a name="07e4_14b2">Theorem 13.6<a name="07e4_14b2"><P>
The average height of a randomly built binary search tree on <I>n</I> distinct keys is <I>O</I>(lg <I>n</I>).<P>
<I><B>Proof     </I></B>Let <I>k</I><SUB>1</SUB>, <I>k</I><SUB>2</SUB>, . . . , <I>k<SUB>n</I></SUB> be a random permutation on the <I>n</I> keys, and let <I>T</I> be the binary search tree that results from inserting the keys in order into an initially empty tree. We first consider the probability that the depth <I>d(k<SUB>j</SUB>, T)</I> of a given key <I>k<SUB>j</I></SUB> is at least <I>t</I>, for an arbitrary value <I>t.</I> By the characterization of <I>d</I> (<I>k<SUB>j</SUB>, T</I>) in Corollary 13.4, if the depth of <I>k<SUB>j</I></SUB> is at least <I>t</I>, then the cardinality of one of the two sets <I>G<SUB>j</I></SUB> and <I>L<SUB>j</I></SUB> must be at least <I>t/</I>2. Thus,<P>
<pre>Pr{<I>d</I>(<I>k<SUB>j</I></SUB>,<I> T</I>)<I> </I><img src="../images/gteq.gif"> <I>t</I>} <img src="../images/lteq12.gif"> Pr{|<I>G<SUB>j</I></SUB>| <img src="../images/gteq.gif"> <I>t</I>/2} + Pr{|<I>L<SUB>j</I></SUB>| <img src="../images/gteq.gif"> <I>t</I>/2} .</sub></sup></pre><P>
<h4><a name="07e4_14b3">(13.2)<a name="07e4_14b3"></sub></sup></h4><P>
Let us examine Pr{|<I>G<SUB>j</SUB></I>|<SUB><img src="../images/gteq.gif"></SUB><I>t</I>/2} first. We have<P>
<pre>Pr{|<I>Gj</I>|<I> </I><img src="../images/gteq.gif"> <I>t</I>/2}</sub></sup></pre><P>
<pre>= Pr{|{k<I><SUB>i</I></SUB>: 1 <img src="../images/lteq12.gif"> <I>i</I> &lt; <I>j</I> and <I>k<SUB>l</I></SUB> &gt; <I>k<SUB>i</I></SUB> &gt; <I>k<SUB>j</I></SUB> for all <I>l</I> &lt; <I>i</I>}| <img src="../images/gteq.gif"> <I>t</I>/2}</sub></sup></pre><P>
<pre><img src="../images/lteq12.gif"> Pr{|{<I>k<SUB>i</I></SUB>: <I>i </I><img src="../images/lteq12.gif"><I> n</I> and <I>k<SUB>i</I></SUB> &gt; k<I>i</I> for all <I>l </I>&gt;<I> i</I>}| <img src="../images/gteq.gif"> <I>t</I>/2}</sub></sup></pre><P>