chap13.htm

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

The pseudocode for <FONT FACE="Courier New" SIZE=2>TREE</FONT>-<FONT FACE="Courier New" SIZE=2>MAXIMUM</FONT> is symmetric.<P>
<pre><a name="07dd_1496">TREE-MAXIMUM (<I>x)</I></sub></sup></pre><P>
<pre>1  <B>while</B> <I>right</I>[<I>x</I>] <img src="../images/noteq.gif"> NIL</sub></sup></pre><P>
<pre>2      <B>do</B> <I>x</I> <img src="../images/arrlt12.gif"> <I>right</I>[<I>x</I>]</sub></sup></pre><P>
<pre>3  <B>return</B> <I>x</I></sub></sup></pre><P>
Both of these procedures run in <I>O</I>(<I>h</I>) time on a tree of height <I>h,</I> since they trace paths downward in the tree.<P>
<P>









<h2>Successor and predecessor</h2><P>
<a name="07de_1497"><a name="07de_1498"><a name="07de_1499"><a name="07de_149a">Given a node in a binary search tree, it is sometimes important to be able to find its successor in the sorted order determined by an inorder tree walk. If all keys are distinct, the successor of a node <I>x</I> is the node with the smallest key greater than <I>key</I>[<I>x</I>]<I>.</I> The structure of a binary search tree allows us to determine the successor of a node without ever comparing keys. The following procedure returns the successor of a node <I>x</I> in a binary search tree if it exists, and <FONT FACE="Courier New" SIZE=2>NIL</FONT> if <I>x</I> has the largest key in the tree.<P>
<pre><a name="07de_149b">TREE SUCCESSOR(<I>x</I>)</sub></sup></pre><P>
<pre>1  <B>if</B> <I>right</I>[<I>x</I>] <img src="../images/noteq.gif"> NIL</sub></sup></pre><P>
<pre>2      <B>then return</B> TREE-MINIMUM(<I>right</I>[<I>x</I>])</sub></sup></pre><P>
<pre>3  <I>y </I><img src="../images/arrlt12.gif"> <I>p</I>[<I>x</I>]</sub></sup></pre><P>
<pre>4  <B>while</B> <I>y </I><img src="../images/noteq.gif"> NIL and <I>x</I> = <I>right</I>[<I>y</I>]</sub></sup></pre><P>
<pre>5       <B>do</B> <I>x </I><img src="../images/arrlt12.gif"> y</sub></sup></pre><P>
<pre>6          <I>y </I><img src="../images/arrlt12.gif"> <I>p</I>[<I>y</I>]</sub></sup></pre><P>
<pre>7  <B>return</B> <I>y</I></sub></sup></pre><P>
The code for <FONT FACE="Courier New" SIZE=2>TREE</FONT>-<FONT FACE="Courier New" SIZE=2>SUCCESSOR</FONT> is broken into two cases. If the right subtree of node <I>x</I> is nonempty, then the successor of <I>x</I> is just the left-most node in the right subtree, which is found in line 2 by calling <FONT FACE="Courier New" SIZE=2>TREE</FONT>-<FONT FACE="Courier New" SIZE=2>MINIMUM</FONT>(<I>right</I>[<I>x</I>]). For example, the successor of the node with key 15 in Figure 13.2 is the node with key 17.<P>
On the other hand, if the right subtree of node <I>x</I> is empty and <I>x</I> has a successor <I>y</I>, then <I>y</I> is the lowest ancestor of <I>x</I> whose left child is also an ancestor of <I>x</I>. In Figure 13.2, the successor of the node with key 13 is the node with key 15. To find <I>y</I>, we simply go up the tree from <I>x</I> until we encounter a<I> </I>node that is the left child of its parent; this is accomplished by lines 3-7 of <FONT FACE="Courier New" SIZE=2>TREE-</FONT><FONT FACE="Courier New" SIZE=2>SUCCESSOR</FONT>.<P>
<a name="07de_149c">The running time of <FONT FACE="Courier New" SIZE=2>TREE-</FONT><FONT FACE="Courier New" SIZE=2>SUCCESSOR</FONT> on a tree of height <I>h</I>is <I>O</I>(<I>h</I>), since we either follow a path up the tree or follow a path down the tree. The procedure <FONT FACE="Courier New" SIZE=2>TREE-</FONT><FONT FACE="Courier New" SIZE=2>PREDECESSOR</FONT>, which is symmetric to <FONT FACE="Courier New" SIZE=2>TREE</FONT>-<FONT FACE="Courier New" SIZE=2>SUCCESSOR</FONT>, also runs in time <I>O</I>(<I>h</I>).<P>
In summary, we have proved the following theorem.<P>
<a name="07de_149d">Theorem 13.1<a name="07de_149d"><P>
The dynamic-set operations <FONT FACE="Courier New" SIZE=2>SEARCH</FONT>, <FONT FACE="Courier New" SIZE=2>MINIMUM</FONT>, <FONT FACE="Courier New" SIZE=2>MAXIMUM</FONT>, <FONT FACE="Courier New" SIZE=2>SUCCESSOR</FONT>, and <FONT FACE="Courier New" SIZE=2>PREDECESSOR</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="07df_149e">Exercises<a name="07df_149e"></h2><P>
<a name="07df_149f">13.2-1<a name="07df_149f"><P>
Suppose that we have numbers between 1 and 1000 in a binary search tree and want to search for the number 363. Which of the following sequences could <I>not</I> be the sequence of nodes examined?<P>
<I><B>a.</I>     </B>2, 252, 401, 398, 330, 344, 397, 363.<P>
<I><B>b.</I>     </B>924, 220, 911, 244, 898, 258, 362, 363.<P>
<I><B>c.</I>     </B>925, 202, 911, 240, 912, 245, 363.<P>
<I><B>d.</I>     </B>2, 399, 387, 219, 266, 382, 381, 278, 363.<P>
<I><B>e.</I>     </B>935, 278, 347, 621, 299, 392, 358, 363.<P>
<a name="07df_14a0">13.2-2<a name="07df_14a0"><P>
Professor Bunyan thinks he has discovered a remarkable property of binary search trees. Suppose that the search for key <I>k </I>in a<I> </I>binary search tree ends up in a leaf. Consider three sets: <I>A</I>, the keys to the left of the search path; <I>B</I>, the keys on the search path; and <I>C</I>, the keys to the right of the search path. Professor Bunyan claims that any three keys <I>a</I> <img src="../images/memof12.gif"> <I>A</I>, <I>b</I> <img src="../images/memof12.gif"> <I>B</I>, and <I>c</I> <img src="../images/memof12.gif"> <I>C</I> must satisfy <I>a</I> <img src="../images/lteq12.gif"> <I>b</I> <img src="../images/lteq12.gif"> <I>c</I>. Give a smallest possible counterexample to the professor's claim.<P>
<a name="07df_14a1">13.2-3<a name="07df_14a1"><P>
Use the binary-search-tree property to prove rigorously that the code for <FONT FACE="Courier New" SIZE=2>TREE-</FONT><FONT FACE="Courier New" SIZE=2>SUCCESSOR</FONT> is correct.<P>
<a name="07df_14a2">13.2-4<a name="07df_14a2"><P>
<a name="07df_149d">An inorder tree walk of an <I>n</I>-node binary search tree can be implemented by finding the minimum element in the tree with <FONT FACE="Courier New" SIZE=2>TREE-</FONT><FONT FACE="Courier New" SIZE=2>MINIMUM</FONT> and then making <I>n</I> - 1 calls to <FONT FACE="Courier New" SIZE=2>TREE-</FONT><FONT FACE="Courier New" SIZE=2>SUCCESSOR</FONT>. Prove that this algorithm runs in <img src="../images/bound.gif">(<I>n</I>) time.<P>
<a name="07df_14a3">13.2-5<a name="07df_14a3"><P>
Prove that no matter what node we start at in a height-<I>h</I> binary search tree, <I>k</I> successive calls to <FONT FACE="Courier New" SIZE=2>TREE-</FONT><FONT FACE="Courier New" SIZE=2>SUCCESSOR</FONT> take <I>O</I>(<I>k</I> + <I>h</I>) time.<P>
<a name="07df_14a4">13.2-6<a name="07df_14a4"><P>
Let <I>T</I> be a binary search tree, let <I>x</I> be a leaf node, and let <I>y</I> be its parent. Show that <I>key</I>[<I>y</I>] is either the smallest key in <I>T</I> larger than <I>key</I>[<I>x</I>] or the largest key in the tree smaller than <I>key</I>[<I>x</I>].<P>
<P>


<P>









<h1><a name="07e0_14a0">13.3 Insertion and deletion<a name="07e0_14a0"></h1><P>
<a name="07e0_149e"><a name="07e0_149f">The operations of insertion and deletion cause the dynamic set represented by a binary search tree to change. The data structure must be modified to reflect this change, but in such a way that the binary-search-tree property continues to hold. As we shall see, modifying the tree to insert a new element is relatively straightforward, but handling deletion is somewhat more intricate.<P>







<h2>Insertion</h2><P>
To insert a new value <I>v</I> into a binary search tree <I>T</I>, we use the procedure <FONT FACE="Courier New" SIZE=2>TREE-</FONT><FONT FACE="Courier New" SIZE=2>INSERT</FONT>. The procedure is passed a node <I>z</I> for which <I>key</I>[<I>z</I>] = <I>v</I>, <I>left</I>[<I>z</I>] = <FONT FACE="Courier New" SIZE=2>NIL</FONT>, and <I>right</I>[<I>z</I>] = <FONT FACE="Courier New" SIZE=2>NIL</FONT>. It modifies <I>T</I> and some of the fields of <I>z</I> in such a way that <I>z</I> is inserted into an appropriate position in the tree.<P>
<pre><a name="07e1_14a0">TREE-INSERT(<I>T</I>,<I>z</I>)</sub></sup></pre><P>
<pre>1  <I>y</I> <img src="../images/arrlt12.gif"> NIL</sub></sup></pre><P>
<pre>2  <I>x</I> <img src="../images/arrlt12.gif"> <I>root</I>[<I>T</I>]</sub></sup></pre><P>
<pre>3  <B>while</B> <I>x</I> <img src="../images/noteq.gif"> NIL</sub></sup></pre><P>
<pre>4       <B>do</B> <I>y</I> <img src="../images/arrlt12.gif"> <I>x</I></sub></sup></pre><P>
<pre>5          <B>if</B> <I>key</I>[<I>z</I>] &lt; <I>key</I>[<I>x</I>]</sub></sup></pre><P>
<pre>6             <B>then</B> <I>x</I> <img src="../images/arrlt12.gif"> <I>left</I>[<I>x</I>]</sub></sup></pre><P>
<pre>7             <B>else</B> <I>x</I> <img src="../images/arrlt12.gif"> <I>right</I>[<I>x</I>]</sub></sup></pre><P>
<pre>8  <I>p</I>[<I>z</I>] <img src="../images/arrlt12.gif"> <I>y</I></sub></sup></pre><P>
<pre>9  <B>if</B> <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>z</I></sub></sup></pre><P>
<pre>11      <B>else if</B> <I>key</I>[<I>z</I>] &lt; <I>key</I>[<I>y</I>]</sub></sup></pre><P>
<pre>12              <B>then</B> <I>left</I>[<I>y</I>] <img src="../images/arrlt12.gif"> <I>z</I></sub></sup></pre><P>
<pre>13              <B>else</B> <I>right</I>[<I>y</I>] <img src="../images/arrlt12.gif"> <I>z</I></sub></sup></pre><P>
Figure 13.3 shows how <FONT FACE="Courier New" SIZE=2>TREE-</FONT><FONT FACE="Courier New" SIZE=2>INSERT</FONT> works. Like the procedures <FONT FACE="Courier New" SIZE=2>TREE-</FONT><FONT FACE="Courier New" SIZE=2>SEARCH</FONT> and <FONT FACE="Courier New" SIZE=2>ITERATIVE</FONT>-<FONT FACE="Courier New" SIZE=2>TREE</FONT>-<FONT FACE="Courier New" SIZE=2>SEARCH</FONT>, <FONT FACE="Courier New" SIZE=2>TREE</FONT>-<FONT FACE="Courier New" SIZE=2>INSERT</FONT> begins at the root of the tree and traces a path downward. The pointer <I>x</I> traces the path, and the pointer <I>y</I> is maintained as the parent of <I>x</I>. After initialization, the <B>while</B> loop in lines 3-7 causes these two pointers to move down the tree, going left or right depending on the comparison of <I>key</I>[<I>z</I>] with <I>key</I>[<I>x</I>], until <I>x</I> is set to <FONT FACE="Courier New" SIZE=2>NIL</FONT>. This <FONT FACE="Courier New" SIZE=2>NIL</FONT> occupies the position where we wish to place the input item <I>z</I>. Lines 8-13 set the pointers that cause <I>z</I> to be inserted.<P>
Like the other primitive operations on search trees, the procedure <FONT FACE="Courier New" SIZE=2>TREE</FONT>-<FONT FACE="Courier New" SIZE=2>INSERT</FONT> runs in <I>O</I>(<I>h</I>) time on a tree of height <I>h</I>.<P>
<P>









<h2>Deletion</h2><P>