📄 chap13.htm
字号:
<pre>= Pr{|<I>S</I>| <I><img src="../images/gteq.gif"></I> t<I>/2} ,</I></sub></sup></pre><P>where <I>S</I> is defined as in equation (13.1). To justify this argument, note that the probability does not decrease if we extend the range of <I>i</I> from <I>i</I> < <I>j</I> to <I>i</I> <img src="../images/lteq12.gif"> <I>n</I>, since more elements are added to the set. Likewise, the probability does not decrease if we remove the condition that <I>k<SUB>i</I></SUB> > <I>k<SUB>j</I></SUB>, since we are substituting a random permutation on possibly fewer than <I>n </I>elements (those <I>k<SUB>i</I></SUB> that are greater than <I>k<SUB>j</I></SUB>) for a random permutation on <I>n</I> elements.<P>Using a symmetric argument, we can prove that<P><pre>Pr{|<I>L<SUB>j</I></SUB>|<SUB> </SUB><img src="../images/gteq.gif"> <SUB><I>t</I>/2} <img src="../images/lteq12.gif"> Pr{|<I>S</I>| <img src="../images/gteq.gif"> <I>t</I>/2},</sub></sup></pre><P>and thus, by inequality (13.2), we obtain<P><pre>Pr {<I>d </I>(<I>k<SUB>j</SUB>, T</I>) <img src="../images/gteq.gif"> <I>t</I>} <img src="../images/lteq12.gif"> 2 Pr{|<I>S</I>| <img src="../images/gteq.gif"> <I>t</I>/2} .</sub></sup></pre><P>If we choose <I>t</I> = 2(<img src="../images/beta14.gif"><I></I> + 1)<I>H<SUB>n</I></SUB>, where <I>H<SUB>n</I></SUB> is the <I>n</I>th harmonic number and <img src="../images/beta14.gif"><I></I> <img src="../images/approx18.gif"> 4.32 satisfies (1n <img src="../images/beta14.gif"><I></I> - l)<img src="../images/beta14.gif"><I></I> = 2, we can apply Lemma 13.5 to conclude that<P><pre>Pr{<I>d</I>(<I>k<SUB>j</SUB>, T</I>) <img src="../images/gteq.gif"> 2(<img src="../images/beta14.gif"><I> + 1)</I>H<SUB>n<I></SUB>} <img src="../images/lteq12.gif"> 2Pr{|</I>S<I>| <img src="../images/gteq.gif"> (<img src="../images/beta14.gif"></I> + 1)<I>H<SUB>n</I></SUB>}</sub></sup></pre><P><pre><img src="../images/lteq12.gif"> 2/<I>n</I><SUP>2 </SUP>.</sub></sup></pre><P>Since there are at most <I>n</I> nodes in a randomly built binary search tree, the probability that <I>any</I> node's depth is at least 2(<img src="../images/beta14.gif"><I></I> + 1 )<I>H<SUB>n</I></SUB> is therefore, by Boole's inequality (6.22), at most <I>n(</I>2<I>/n</I><SUP>2</SUP><I>)</I> = 2/<I>n</I>. Thus, at least 1 - 2/<I>n </I>of the time, the height of a randomly built binary search tree is less than 2(<img src="../images/beta14.gif"><I></I> + 1)<I>H<SUB>n</I></SUB>, and at most 2/<I>n</I> of the time, it is at most <I>n</I>. The expected height is therefore at most (2(<img src="../images/beta14.gif"><I></I> + 1)<I>H<SUB>n</I></SUB>)(l - 2/<I>n</I>) + <I>n</I>(2/<I>n</I>) = <I>O(lg n)</I>. <P><h2><a name="07e5_14ae">Exercises<a name="07e5_14ae"></h2><P><a name="07e5_14af">13.4-1<a name="07e5_14af"><P>Describe a binary search tree on <I>n</I> nodes such that the average depth of a node in the tree is <img src="../images/bound.gif">(lg <I>n</I>) but the height of the tree is <I>w</I>(lg <I>n</I>). How large can the height of an <I>n</I>-node binary search tree be if the average depth of a node is <img src="../images/bound.gif">(lg <I>n</I>)?<P><a name="07e5_14b0">13.4-2<a name="07e5_14b0"><P>Show that the notion of a randomly chosen binary search tree on <I>n</I> keys, where each binary search tree of <I>n</I> keys is equally likely to be chosen, is different from the notion of a randomly built binary search tree given in this section. (<I>Hint:</I> List the possibilities when <I>n</I> = 3.)<P><a name="07e5_14b1">13.4-3<a name="07e5_14b1"><P>Given a constant <I>r</I> <img src="../images/gteq.gif"> 1, determine <I>t</I> such that the probability is less than 1 /<I>n<SUP>r</I></SUP> that the height of a randomly built binary search tree is at least <I>tH<SUB>n</I></SUB>.<P><a name="07e5_14b2">13.4-4<a name="07e5_14b2"><P><a name="07e5_14ac"><a name="07e5_14ad">Consider <FONT FACE="Courier New" SIZE=2>RANDOMIZED</FONT>-<FONT FACE="Courier New" SIZE=2>QUICKSORT</FONT> operating on a sequence of <I>n</I> input numbers. Prove that for any constant <I>k</I> > 0, all but <I>O</I>(l/<I>n<SUP>k</I></SUP>) of the <I>n</I>! input permutations yield an <I>O</I>(<I>n</I>1g <I>n</I>) running time.<P><P><P><h1><a name="07e6_14be">Problems<a name="07e6_14be"></h1><P><a name="07e6_14bf">13-1 Binary search trees with equal keys<a name="07e6_14bf"><P><a name="07e6_14ae"><a name="07e6_14af"><a name="07e6_14b0">Equal keys pose a problem for the implementation of binary search trees.<P><I><B>a</I>.</B> What is the asymptotic performance of <FONT FACE="Courier New" SIZE=2>TREE</FONT>-<FONT FACE="Courier New" SIZE=2>INSERT</FONT> when used to insert <I>n</I> items with identical keys into an initially empty binary search tree?<P>We propose to improve <FONT FACE="Courier New" SIZE=2>TREE</FONT>-<FONT FACE="Courier New" SIZE=2>INSERT</FONT> by testing before line 5 whether or not <I>key</I>[<I>z</I>] = <I>key</I>[<I>x</I>] and by testing before line 11 whether or not <I>key</I>[<I>z</I>] =<I> key</I>[<I>y</I>]. If equality holds, we implement one of the following strategies. For each strategy, find the asymptotic performance of inserting <I>n</I> items with identical keys into an initially empty binary search tree. (The strategies are described for line 5, in which we compare the keys of <I>z</I> and <I>x</I>. Substitute<I> y</I> for <I>x</I> to arrive at the strategies for line 11.)<P><I><B>b</I>.</B> Keep a Boolean flag <I>b</I>[<I>x</I>] at node <I>x</I>, and set <I>x</I> to either <I>left</I>[<I>x</I>] or <I>right</I>[<I>x</I>]based on the value of <I>b</I>[<I>x</I>], which alternates between <FONT FACE="Courier New" SIZE=2>FALSE</FONT> and <FONT FACE="Courier New" SIZE=2>TRUE</FONT> each time the node is visited during <FONT FACE="Courier New" SIZE=2>TREE</FONT>-<FONT FACE="Courier New" SIZE=2>INSERT</FONT>.<P><I><B>c.</I> </B>Keep a list of nodes with equal keys at <I>x</I>, and insert <I>z</I> into the list.<P><I><B>d</I>.</B> Randomly set <I>x</I> to either <I>left</I>[<I>x</I>] or <I>right</I>[<I>x</I>]. (Give the worst-case performance and informally derive the average-case performance.)<P><a name="07e6_14c0">13-2 Radix trees<a name="07e6_14c0"><P><a name="07e6_14b1"><a name="07e6_14b2"><a name="07e6_14b3"><a name="07e6_14b4"><a name="07e6_14b5">Given two strings <I>a</I> = <I>a<SUB>0</SUB>a</I><SUB>1</SUB>. . .<I>a<SUB>p</I></SUB> and <I>b</I> = <I>b</I><SUB>0</SUB><I>b</I><SUB>1</SUB><I>. . .bq</I>,<I> where each a<SUB>i</I></SUB> and each <I>b<SUB>j</I></SUB> is in some ordered set of characters, we say that string <I>a </I>is<I> <B>lexicographically less than</I></B> string <I>b</I> if either<P>1. there exists an integer <I>j</I>, 0 <img src="../images/lteq12.gif"> <I>j</I> <img src="../images/lteq12.gif"> min(<I>p, q</I>), such that <I>a<SUB>i</I></SUB> = <I>b<SUB>i</I></SUB> for all<I> i = </I>0, 1<I>, . . . , j</I> - 1 and <I>a<SUB>j</I></SUB> < <I>b<SUB>j</I></SUB>, or<P>2.<I> p<q</I> and <I>a<SUB>i </I></SUB>= <I>b<SUB>i</I></SUB> for all <I>i </I>= 0, l, . . . , <I>p</I>.<P>For example, if <I>a</I> and <I>b</I> are bit strings, then 10100 < 10110 by rule 1(letting <I>j</I> = 3) and 10100 < 101000 by rule 2. This is similar to the ordering used in English-language dictionaries.<P>The <I><B>radix tree</I></B> data structure shown in Figure 13.6 stores the bit strings 1011, 10, 011, 100, and 0. When searching for a key <I>a</I> = <I>a</I><SUB>0</SUB><I>a</I><SUB>1</SUB> . . . <I>a<SUB>p</I></SUB>, we go left at a node of depth <I>i</I> if <I>a<SUB>i</I></SUB> = 0 and right if <I>a<SUB>i</I></SUB> = 1. Let <I>S</I> be a set of distinct binary strings whose lengths sum to <I>n</I>. Show how to use a radix tree to sort <I>S</I> lexicographically in <img src="../images/bound.gif">(<I>n</I>) time. For the example in Figure 13.6, the output of the sort should be the sequence 0, 011, 10, 100, 1011.<P><a name="07e6_14c1">13-3 Average node depth in a randomly built binary search tree<a name="07e6_14c1"><P><a name="07e6_14b6"><a name="07e6_14b7"><a name="07e6_14b8"><a name="07e6_14b9"><a name="07e6_14ba">In this problem, we prove that the average depth of a node in a randomly built binary search tree with <I>n</I> nodes is <I>O(</I>lg <I>n)</I>. Although this result is weaker than that of Theorem 13.6, the technique we shall use reveals a surprising similarity between the building of a binary search tree and the running of <FONT FACE="Courier New" SIZE=2>RANDOMIZED</FONT>-<FONT FACE="Courier New" SIZE=2>QUICKSORT</FONT> from Section 8.3.<P>We start by recalling from Chapter 5 that the internal path length <I>P</I>(<I>T</I>)of a binary tree <I>T</I> is the sum, over all nodes <I>x</I> in <I>T</I>, of the depth of node <I>x</I>, which we denote by <I>d </I>(<I>x, T</I>).<P><img src="261_a.gif"><P><h4><a name="07e6_14c2">Figure 13.6 A radix tree storing the bit strings l011, 10, 011, 100, and 0. Each node's key can be determined by traversing the path from the root to that node. There is no need, therefore, to store the keys in the nodes; the keys are shown here for illustrative purposes only. Nodes are heavily shaded if the keys corresponding to them are not in the tree; such nodes are present only to establish a path to other nodes.<a name="07e6_14c2"></sub></sup></h4><P><I><B>a.</I></B> Argue that the average depth of a node in <I>T</I> is<P><img src="261_b.gif"><P>Thus, we wish to show that the expected value of <I>P</I>(<I>T</I>) is <I>O</I>(<I>n </I>1g<I> n</I>).<P><I><B>b.</I> </B>Let <I>T<SUB>L</I></SUB> and <I>T<SUB>R</I></SUB> denote the left and right subtrees of tree <I>T</I>, respectively. Argue that if <I>T</I> has <I>n</I> nodes, then<P><pre><I>P</I>(<I>T</I>) = <I>P</I>(<I>T<SUB>L</I></SUB>) + <I>P</I>(<I>T<SUB>R</I></SUB>) + <I>n</I> - 1 .</sub></sup></pre><P><I><B>c.</I> </B>Let <I>P</I>(<I>n</I>) denote the average internal path length of a randomly built binary search tree with <I>n</I> nodes. Show that<P><img src="261_c.gif"><P><I><B>d. </I></B>Show that <I>P</I>(<I>n</I>) can be rewritten as<P><img src="261_d.gif"><P><I><B>e. </I></B>Recalling the analysis of the randomized version of quicksort, conclude that <I>P</I>(<I>n</I>) = <I>O</I>(<I>n </I>lg <I>n</I>).<P>At each recursive invocation of quicksort, we choose a random pivot element to partition the set of elements being sorted. Each node of a binary search tree partitions the set of elements that fall into the subtree rooted at that node.<P><I><B>f.</I> </B>Describe an implementation of quicksort in which the comparisons to sort a set of elements are exactly the same as the comparisons to insert the elements into a binary search tree. (The order in which comparisons are made may differ, but the same comparisons must be made.)<P><a name="07e6_14c3">13-4 Number of different binary trees<a name="07e6_14c3"><P><a name="07e6_14bb">Let <I>b<SUB>n</I></SUB> denote the number of different binary trees with <I>n</I> nodes. In this problem, you will find a formula for <I>b<SUB>n</I></SUB> as well as an asymptotic estimate.<P><I><B>a. </I></B>Show that <I>b</I><SUB>0</SUB> = 1 and that, for <I>n</I> <img src="../images/gteq.gif"> 1,<P><img src="262_a.gif"><P><I><B>b </I></B>Let <I>B</I>(<I>x</I>) be the generating function<P><img src="262_b.gif"><P>(see Problem 4-6 for the definition of generating functions). Show that <I>B</I>(<I>x</I>) = <I>xB</I>(<I>x</I>)<SUP>2</SUP> + 1 and hence<P><img src="262_c.gif"><P><a name="07e6_14bc">The <I><B>Taylor expansion</I></B> of <I>f</I>(<I>x</I>) around the point <I>x</I> = <I>a</I> is given by<P><img src="262_d.gif"><P>where<SUB> </SUB><I>f</I><SUP>(<I>k</I>)</SUP> (<I>x</I>) is the <I>k</I>th derivative of <I>f</I> evaluated at <I>x</I>.<P><I><B>c.</I> </B>Show that<P><img src="262_e.gif"><P><a name="07e6_14bd">(the <I>n</I>th <I><B>Catalan number</I></B>) by using the Taylor expansion of <img src="262_f.gif"> around <I>x</I> = 0. (If you wish,<SUB> </SUB>instead of using the Taylor expansion, you may use the generalization of the binomial expansion (6.5) to<SUB> </SUB>non-integral exponents <I>n</I>, where for any real number <I>n</I> and integer <I>k</I>, we interpret <img src="262_g.gif"> to be <I>n</I>(<I>n</I> - 1) . . . (<I>n</I> - <I>k</I> + 1)/<I>k</I>! if <I>k</I> <img src="../images/gteq.gif"> 0, and 0 otherwise.)<P><I><B>d.</I> </B>Show that<P><img src="262_h.gif"><P><P><h1>Chapter notes</h1><P>Knuth [123] contains a good discussion of simple binary search trees as well as many variations. Binary search trees seem to have been independently discovered by a number of people in the late 1950's.<P><P><P><P><center>Go to <a href="chap14.htm">Chapter 14</A> Back to <a href="toc.htm">Table of Contents</A></P></center></BODY></HTML>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -