chap11.htm

介绍算法的书籍

<h2>Other tree representations</h2><P>
We sometimes represent rooted trees in other ways. In Chapter 7, for example, we represented a heap, which is based on a complete binary tree, by a single array plus an index. The trees that appear in Chapter 22 are only traversed toward the root, so only the parent pointers are present; there are no pointers to children. Many other schemes are possible. Which scheme is best depends on the application.<P>
<img src="215_a.gif"><P>
<h4><a name="07bc_0001">Figure 11.10 The left-child, right-sibling representation of a tree T. Each node x has fields p[x] (top), left-child[x] (lower left), and right-sibling[x] (lower right). Keys are not shown.<a name="07bc_0001"></sub></sup></h4><P>
<P>







<h2><a name="07bd_141f">Exercises<a name="07bd_141f"></h2><P>
<a name="07bd_1420">11.4-1<a name="07bd_1420"><P>
<a name="07bd_141b"><a name="07bd_141c"><a name="07bd_141d">Draw the binary tree rooted at index 6 that is represented by the following fields.<P>
<pre><I>index  key  left  right</I></sub></sup></pre><P>
<pre>----------------------</sub></sup></pre><P>
<pre>   1    12   7     3</sub></sup></pre><P>
<pre>   2    15   8    NIL</sub></sup></pre><P>
<pre>   3     4  10    NIL</sub></sup></pre><P>
<pre>   4    10   5     9</sub></sup></pre><P>
<pre>   5     2  NIL   NIL</sub></sup></pre><P>
<pre>   6    18   1    4</sub></sup></pre><P>
<pre>   7     7  NIL   NIL</sub></sup></pre><P>
<pre>   8    14   6    2</sub></sup></pre><P>
<pre>   9    21  NIL   NIL</sub></sup></pre><P>
<pre>  10     5  NIL   NIL</sub></sup></pre><P>
<a name="07bd_1421">11.4-2<a name="07bd_1421"><P>
Write an <I>O</I>(<I>n</I>)-time recursive procedure that, given an <I>n</I>-node binary tree, prints out the key of each node in the tree.<P>
<a name="07bd_1422">11.4-3<a name="07bd_1422"><P>
Write an <I>O</I>(<I>n</I>)-time nonrecursive procedure that, given an <I>n</I>-node binary tree, prints out the key of each node in the tree. Use a stack as an auxiliary data structure.<P>
<a name="07bd_1423">11.4-4<a name="07bd_1423"><P>
Write an <I>O</I>(<I>n</I>)-time procedure that prints all the keys of an arbitrary rooted tree with <I>n</I> nodes, where the tree is stored using the left-child, right-sibling representation.<P>
<a name="07bd_1424">11.4-5<a name="07bd_1424"><P>
Write an <I>O</I>(<I>n</I>)-time nonrecursive procedure that, given an <I>n</I>-node binary tree, prints out the key of each node. Use no more than constant extra space outside of the tree itself and do not modify the tree, even temporarily, during the procedure.<P>
<a name="07bd_1425">11.4-6<a name="07bd_1425"><P>
<a name="07bd_141e">The left-child, right-sibling representation of an arbitrary rooted tree uses three pointers in each node: <I>left-child, right-sibling</I>, and <I>parent</I>. From any node, the parent and all the children of the node can be reached and identified. Show how to achieve the same effect using only two pointers and one boolean value in each node.<P>
<P>


<P>







<h1><a name="07be_1426">Problems<a name="07be_1426"></h1><P>
<a name="07be_1427">11-1     Comparisons among lists<a name="07be_1427"><P>
For each of the four types of lists in the following table, what is the asymptotic worst-case running time for each dynamic-set operation listed?<P>
<pre>                   unsorted,  sorted,  unsorted,  sorted,</sub></sup></pre><P>
<pre>                    singly    singly    doubly    doubly</sub></sup></pre><P>
<pre>                    linked    linked    linked    linked</sub></sup></pre><P>
<pre>---------------------------------------------------------</sub></sup></pre><P>
<pre>SEARCH(<I>L</I>,<I>k</I>)</sub></sup></pre><P>
<pre>INSERT(<I>L</I>,<I>x</I>)</sub></sup></pre><P>
<pre>DELETE(<I>L,x</I>)</sub></sup></pre><P>
<pre>SUCCESSOR(<I>L</I>,<I>x</I>)</sub></sup></pre><P>
<pre>PREDECESSOR(<I>L</I>,<I>x</I>)</sub></sup></pre><P>
<pre>MINIMUM(<I>L</I>)</sub></sup></pre><P>
<pre>MAXIMUM(<I>L</I>)</sub></sup></pre><P>
<a name="07be_1428">11-2     Mergeable heaps using linked lists<a name="07be_1428"><P>
<a name="07be_141f">A <I><B>mergeable heap</I></B> supports the following operations: <FONT FACE="Courier New" SIZE=2>MAKE</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT> (which creates an empty mergeable heap), <FONT FACE="Courier New" SIZE=2>INSERT</FONT>, <FONT FACE="Courier New" SIZE=2>MINIMUM</FONT>, <FONT FACE="Courier New" SIZE=2>EXTRACT</FONT>-<FONT FACE="Courier New" SIZE=2>MIN</FONT>, and <FONT FACE="Courier New" SIZE=2>UNION</FONT>. Show how to implement mergeable heaps using linked lists in each of the following cases. Try to make each operation as efficient as possible. Analyze the running time of each operation in terms of the size of the dynamic set(s) being operated on.<P>
<I><B>a.     </I></B>Lists are sorted.<P>
<I><B>b.     </I></B>Lists are unsorted.<P>
<I><B>c.     </I></B>Lists are unsorted, and dynamic sets to be merged are disjoint.<P>
<a name="07be_1429">11-3     Searching a sorted compact list<a name="07be_1429"><P>
<a name="07be_1420"><a name="07be_1421"><a name="07be_1422"><a name="07be_1423"><a name="07be_1424"><a name="07be_1425">Exercise 11.3-4 asked how we might maintain an <I>n</I>-element list compactly in the first <I>n</I> positions of an array. We shall assume that all keys are distinct and that the compact list is also sorted, that is, <I>key</I>[<I>i</I>]<I> &lt; key</I>[<I>next</I>[<I>i</I>]] for all <I>i</I> = 1, 2, . . . , <I>n</I> such that <I>next</I>[<I>i</I>] <img src="../images/noteq.gif"> <FONT FACE="Courier New" SIZE=2>NIL</FONT>. Under these assumptions, we expect that the following randomized algorithm can be used to search the list much faster than linear time.<P>
<pre>COMPACT-LIST-SEARCH(<I>L</I>, <I>k</I>)</sub></sup></pre><P>
<pre>1  <I>i</I> <img src="../images/arrlt12.gif"> <I>head</I>[<I>L</I>]</sub></sup></pre><P>
<pre>2  <I>n</I> <img src="../images/arrlt12.gif"> <I>length</I>[<I>L</I>]</sub></sup></pre><P>
<pre>3  <B>while</B> <I>i</I> <img src="../images/noteq.gif"> NIL and <I>key</I>[<I>i</I>] &lt; <I>k</I></sub></sup></pre><P>
<pre>4      <B>do</B> <I>j</I> <img src="../images/arrlt12.gif"> RANDOM(l, <I>n</I>)</sub></sup></pre><P>
<pre>5<B>         if</B> <I>key</I>[<I>i</I>] &lt; <I>key</I>[<I>j</I>] and <I>key</I>[<I>j</I>] &lt; <I>k</I></sub></sup></pre><P>
<pre>6<B>            then</B> <I>i</I> <img src="../images/arrlt12.gif"> <I>j</I></sub></sup></pre><P>
<pre>7         <I>i</I> <img src="../images/arrlt12.gif"> <I>next</I>[<I>i</I>]</sub></sup></pre><P>
<pre>8<B>         if</B> <I>key</I>[<I>i</I>] = <I>k</I></sub></sup></pre><P>
<pre>9<B>            then return</B> <I>i</I></sub></sup></pre><P>
<pre>10  <B>return</B> NIL</sub></sup></pre><P>
If we ignore lines 4-6 of the procedure, we have the usual algorithm for searching a sorted linked list, in which index <I>i</I> points to each position of the list in turn. Lines 4-6 attempt to skip ahead to a randomly chosen position <I>j</I>. Such a skip is beneficial if <I>key</I>[<I>j</I>] is larger than <I>key</I>[<I>i</I>] and smaller than <I>k</I>; in such a case, <I>j</I> marks a position in the list that <I>i</I> would have to pass by during an ordinary list search. Because the list is compact, we know that any choice of <I>j</I> between 1 and <I>n</I> indexes some object in the list rather than a slot on the free list.<P>
<I><B>a.</I></B>     Why do we assume that all keys are distinct in <FONT FACE="Courier New" SIZE=2>COMPACT</FONT>-<FONT FACE="Courier New" SIZE=2>LIST</FONT>-<FONT FACE="Courier New" SIZE=2>SEARCH</FONT>? Argue that random skips do not necessarily help asymptotically when the list contains repeated key values.<P>
We can analyze the performance of <FONT FACE="Courier New" SIZE=2>COMPACT</FONT>-<FONT FACE="Courier New" SIZE=2>LIST</FONT>-<FONT FACE="Courier New" SIZE=2>SEARCH</FONT> by breaking its execution into two phases. During the first phase, we discount any progress toward finding <I>k</I> that is accomplished by lines 7-9. That is, phase 1 consists of moving ahead in the list by random skips only. Likewise, phase 2 discounts progress accomplished by lines 4-6, and thus it operates like ordinary linear search.<P>
Let <I>X<SUB>t</I> </SUB>be the random variable that describes the distance in the linked list (that is, through the chain of <I>next</I> pointers) from position <I>i</I> to the desired key <I>k</I> after <I>t</I> iterations of phase l.<P>
<I><B>b.</I></B>     Argue that the expected running time of <FONT FACE="Courier New" SIZE=2>COMPACT</FONT>-<FONT FACE="Courier New" SIZE=2>LIST</FONT>-<FONT FACE="Courier New" SIZE=2>SEARCH</FONT> is <I>O</I>(<I>t+</I>E<I> </I>[<I>X<SUB>t</I></SUB>]) for all <I>t </I><img src="../images/gteq.gif"> 0.<P>
<I><B>c.</I></B>     Show that <img src="218_a.gif">. (<I>Hint</I>. Use equation (6.28).)<P>
<I><B>d.</I></B>     Show that <img src="218_b.gif"><P>
<I><B>e.</I></B>     Prove that E[<I>X<SUB>t</I></SUB>] <img src="../images/lteq12.gif"> <I>n</I>/(<I>t + </I>1), and explain why this formula makes intuitive sense.<P>
<I><B>f.</I></B>     Show that <FONT FACE="Courier New" SIZE=2>COMPACT</FONT>-<FONT FACE="Courier New" SIZE=2>LIST</FONT>-<FONT FACE="Courier New" SIZE=2>SEARCH</FONT> runs in <img src="218_c.gif"> expected time.<P>
<P>







<h1>Chapter notes</h1><P>
Aho, Hopcroft, and Ullman [5] and Knuth [121] are excellent references for elementary data structures. Gonnet [90] provides experimental data on the performance of many data structure operations.<P>
The origin of stacks and queues as data structures in computer science is unclear, since corresponding notions already existed in mathematics and paper-based business practices before the introduction of digital computers. Knuth [121] cites A. M. Turing for the development of stacks for subroutine linkage in 1947.<P>
Pointer-based data structures also seem to be a folk invention. According to Knuth, pointers were apparently used in early computers with drum memories. The A-l language developed by G. M. Hopper in 1951 represented algebraic formulas as binary trees. Knuth credits the IPL-II language, developed in 1956 by A. Newell, J. C. Shaw, and H. A. Simon, for recognizing the importance and promoting the use of pointers. Their IPL-III language, developed in 1957, included explicit stack operations.<P>
<P>


<P>
<P>
<center>Go to <a href="chap12.htm">Chapter 12</A>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Back to <a href="toc.htm">Table of Contents</A>
</P>
</center>


</BODY></HTML>