chap14.htm

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

<a name="07ef_0003">14.3-2<a name="07ef_0003"><P>
In line 18 of RB-<FONT FACE="Courier New" SIZE=2>INSERT</FONT>, we set the root's color to black. What is the advantage of doing so?<P>
<a name="07ef_0004">14.3-3<a name="07ef_0004"><P>
Show the red-black trees that result after successively inserting the keys 41, 38, 31, 12, 19, 8 into an initially empty red-black tree.<P>
<a name="07ef_0005">14.3-4<a name="07ef_0005"><P>
Suppose that the black-height of each of the subtrees<I> </I><img src="../images/alpha12.gif">, <I><img src="../images/beta14.gif">, </I><img src="../images/gamma14.gif">, <I><img src="../images/delta12.gif">, </I><img src="../images/epsilon.gif"><I></I> in Figures 14.5 and 14.6 is <I>k</I>. Label each node in each figure with its black-height to verify that property 4 is preserved by the indicated transformation.<P>
<a name="07ef_0006">14.3-5<a name="07ef_0006"><P>
Consider a red-black tree formed by inserting <I>n</I> nodes with <FONT FACE="Courier New" SIZE=2>RB-INSERT</FONT>. Argue that if <I>n</I> &gt; 1, the tree has at least one red node.<P>
<a name="07ef_0007">14.3-6<a name="07ef_0007"><P>
Suggest how to implement <FONT FACE="Courier New" SIZE=2>RB-INSERT</FONT> efficiently if the representation for red-black trees includes no storage for parent pointers.<P>
<P>


<P>









<h1><a name="07f0_14e1">14.4 Deletion<a name="07f0_14e1"></h1><P>
<a name="07f0_14db"><a name="07f0_14dc">Like the other basic operations on an <I>n</I>-node red-black tree, deletion of a node takes time <I>O</I>(lg <I>n</I>). Deleting a node from a red-black tree is only slightly more complicated than inserting a node.<P>
<a name="07f0_14dd">In order to simplify boundary conditions in the code, we use a sentinel to represent <FONT FACE="Courier New" SIZE=2>NIL</FONT> (see page 206). For a red-black tree <I>T,</I> the sentinel <I>nil</I>[<I>T</I>]<I> </I>is an object with the same fields as an ordinary node in the tree. Its <I>color</I> field is <FONT FACE="Courier New" SIZE=2>BLACK</FONT>, and its other fields--<I>p, left, right,</I> and <I>key</I>--can be set to arbitrary values. In the red-black tree, all pointers to <FONT FACE="Courier New" SIZE=2>NIL</FONT> are replaced by pointers to the sentinel <I>nil</I>[<I>T</I>]<I>.</I><P>
We use sentinels so that we can treat a <FONT FACE="Courier New" SIZE=2>NIL</FONT> child of a node <I>x</I> as an ordinary node whose parent is <I>x.</I> We could add a distinct sentinel node for each <FONT FACE="Courier New" SIZE=2>NIL</FONT> in the tree, so that the parent of each <FONT FACE="Courier New" SIZE=2>NIL</FONT> is well defined, but that would waste space. Instead, we use the one sentinel <I>nil</I>[<I>T</I>] to represent all the <FONT FACE="Courier New" SIZE=2>NIL'S</FONT>. When we wish to manipulate a child of a node <I>x, </I>however, we must be careful to set <I>p</I>[<I>nil</I>[<I>T</I>]] to <I>x</I> first.<P>
<a name="07f0_14de"><a name="07f0_14df"><a name="07f0_14e0">The procedure RB-<FONT FACE="Courier New" SIZE=2>DELETE</FONT> is a minor modification of the <FONT FACE="Courier New" SIZE=2>TREE</FONT>-<FONT FACE="Courier New" SIZE=2>DELETE</FONT> procedure (Section 13.3). After splicing out a node, it calls an auxiliary procedure RB-<FONT FACE="Courier New" SIZE=2>DELETE</FONT>-<FONT FACE="Courier New" SIZE=2>FIXUP</FONT> that changes colors and performs rotations to restore the red-black properties.<P>
<pre>RB-DELETE (<I>T, z</I>)</sub></sup></pre><P>
<pre>1 <B>if</B> left[z] = nil[T] or right[z] = nil[T]</sub></sup></pre><P>
<pre>2      <B>then</B> y <img src="../images/arrlt12.gif"> z</sub></sup></pre><P>
<pre>3      <B>else</B> y <img src="../images/arrlt12.gif"> TREE-SUCCESSOR(z)</sub></sup></pre><P>
<pre>4 <B>if</B> left[y] <img src="../images/noteq.gif"> nil[T]     </sub></sup></pre><P>
<pre>5     <B>then</B> x <img src="../images/arrlt12.gif"> left[y]</sub></sup></pre><P>
<pre>6     <B>else</B> x <img src="../images/arrlt12.gif"> right[y]</sub></sup></pre><P>
<pre>7 p[x] <img src="../images/arrlt12.gif"> p[y]</sub></sup></pre><P>
<pre>8 <B>if</B> p[y] = nil[T]</sub></sup></pre><P>
<pre>9    <B>then</B> root[T] <img src="../images/arrlt12.gif"> x</sub></sup></pre><P>
<pre>10    <B>else if</B> <I>y = left</I>[<I>p</I>[<I>y</I>]]</sub></sup></pre><P>
<pre>11            <B>then</B> <I>left</I>[<I>p</I>[<I>y</I>]]<I> </I><img src="../images/arrlt12.gif"> x</sub></sup></pre><P>
<pre>12            <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>13 <B>if</B> <I>y </I><img src="../images/noteq.gif"> z</sub></sup></pre><P>
<pre>14     <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>15          <img src="273_a.gif"> If <I>y</I> has other fields, copy them, too.</sub></sup></pre><P>
<pre>16 <B>if</B> <I>color</I>[<I>y</I>] = BLACK</sub></sup></pre><P>
<pre>17     <B>then</B> RB-DELETE-FIXUP (<I>T,x</I>)</sub></sup></pre><P>
<pre>18 <B>return</B> <I>y</I></sub></sup></pre><P>
There are three differences between the procedures <FONT FACE="Courier New" SIZE=2>TREE</FONT>-<FONT FACE="Courier New" SIZE=2>DELETE</FONT> and RB-<FONT FACE="Courier New" SIZE=2>DELETE</FONT>. First, all references to <FONT FACE="Courier New" SIZE=2>NIL</FONT> in <FONT FACE="Courier New" SIZE=2>TREE</FONT>-<FONT FACE="Courier New" SIZE=2>DELETE</FONT> have been replaced by references to the sentinel <I>nil</I>[<I>T</I>] in RB-<FONT FACE="Courier New" SIZE=2>DELETE</FONT>. Second, the test for whether <I>x</I> is <FONT FACE="Courier New" SIZE=2>NIL</FONT> in line 7 of <FONT FACE="Courier New" SIZE=2>TREE</FONT>-<FONT FACE="Courier New" SIZE=2>DELETE</FONT> has been removed, and the assignment <I>p</I>[<I>x</I>]<I> </I><img src="../images/arrlt12.gif"><I> p</I>[<I>y</I>] is performed unconditionally in line 7 of RB-<FONT FACE="Courier New" SIZE=2>DELETE</FONT>. Thus, if <I>x</I> is the sentinel <I>nil</I>[<I>T</I>], its parent pointer points to the parent of the spliced-out node <I>y</I>. Third, a call to RB-<FONT FACE="Courier New" SIZE=2>DELETE</FONT>-<FONT FACE="Courier New" SIZE=2>FIXUP</FONT> is made in lines 16-17 if <I>y</I> is black. If <I>y</I> is red, the red-black properties still hold when <I>y</I> is spliced out, since no black-heights in the tree have changed and no red nodes have been made adjacent. The node <I>x</I> passed to RB-<FONT FACE="Courier New" SIZE=2>DELETE-FIXUP</FONT> is the node that was <I>y</I>'s sole child before <I>y</I> was spliced out if <I>y</I> had a non-<FONT FACE="Courier New" SIZE=2>NIL</FONT> child, or the sentinel <I>nil</I>[<I>T</I>] if <I>y</I> had no children. In the latter case, the unconditional assignment in line 7 guarantees that <I>x</I>'s parent is now the node that was previously <I>y</I>'s parent, whether <I>x</I> is a key-bearing internal node or the sentinel <I>nil</I>[<I>T</I>].<P>
We can now examine how the procedure RB-<FONT FACE="Courier New" SIZE=2>DELETE</FONT>-<FONT FACE="Courier New" SIZE=2>FIXUP</FONT> restores the red-black properties to the search tree.<P>
<img src="274_a.gif"><P>
If the spliced-out node <I>y</I> in RB-<FONT FACE="Courier New" SIZE=2>DELETE</FONT> is black, its removal causes any path that previously contained node <I>y</I> to have one fewer black node. Thus, property 4 is now violated by any ancestor of <I>y</I> in the tree. We can correct this problem by thinking of node <I>x</I> as having an &quot;extra&quot; black. That is, if we add 1 to the count of black nodes on any path that contains <I>x</I>, then under this interpretation, property 4 holds. When we splice out the black node <I>y</I>, we <FONT FACE="CG Times (W1)" SIZE=2>&quot;</FONT>push&quot; its blackness onto its child. The only problem is that now node <I>x</I> may be &quot;doubly black,&quot; thereby violating property 1.<P>
The procedure RB-<FONT FACE="Courier New" SIZE=2>DELETE</FONT>-<FONT FACE="Courier New" SIZE=2>FIXUP</FONT> attempts to restore property 1. The goal of the <B>while</B> loop in lines 1-22 is to move the extra black up the tree until (1) <I>x</I> points to a red node, in which case we color the node black in line 23, (2) <I>x</I> points to the root, in which case the extra black can be simply <FONT FACE="CG Times (W1)" SIZE=2>&quot;</FONT>removed,&quot; or (3) suitable rotations and recolorings can be performed.<P>
Within the <B>while</B> loop, <I>x</I> always points to a nonroot black node that has the extra black. We determine in line 2 whether <I>x</I> is a left child or a right child of its parent <I>p</I>[<I>x</I>]. (We have given the code for the situation in which <I>x</I> is a left child; the situation in which <I>x</I> is a right child--line 22--is symmetric.) We maintain a pointer <I>w</I> to the sibling of <I>x</I>. Since node <I>x</I> is doubly black, node <I>w</I> cannot be <I>nil</I>[<I>T</I>]; otherwise, the number of blacks on the path from <I>p</I>[<I>x</I>] to the <FONT FACE="Courier New" SIZE=2>NIL</FONT> leaf <I>w</I> would be smaller than the number on the path from <I>p</I>[<I>x</I>] to <I>x</I>.<P>
The four cases in the code are illustrated in Figure 14.7. Before examining each case in detail, let's look more generally at how we can verify that the transformation in each of the cases preserves property 4. The key idea is that in each case the number of black nodes from (and including) the root of the subtree shown to each of the subtrees <img src="../images/alpha12.gif">, <I><img src="../images/beta14.gif">,</I> . . ., <img src="../images/zeta12.gif"><I></I> is preserved by the transformation. For example, in Figure 14.7(a), which illustrates case 1, the number of black nodes from the root to either subtree <img src="../images/alpha12.gif"><I> or <img src="../images/beta14.gif"></I> is 3, both before and after the transformation. (Remember, the pointer <I>x</I> adds an extra black.) Similarly, the number of black nodes from the root to any of <img src="../images/gamma14.gif">, <I><img src="../images/delta12.gif">, </I><img src="../images/epsilon.gif">,<I> and <img src="../images/zeta12.gif"></I> is 2, both before and after the transformation. In Figure 14.7(b), the counting must involve the color <I>c</I>, which can be either red or black. If we define count(<FONT FACE="Courier New" SIZE=2>RED</FONT>) = 0 and count(<FONT FACE="Courier New" SIZE=2>BLACK</FONT>) = 1, then the number of black nodes from the root to <img src="../images/alpha12.gif"><I></I> is 2 + count(<I>c</I>), both before and after the transformation. The other cases can be verified similarly (Exercise 14.4-5).<P>
Case 1 (lines 5-8 of RB-<FONT FACE="Courier New" SIZE=2>DELETE</FONT>-<FONT FACE="Courier New" SIZE=2>FIXUP</FONT> and Figure 14.7(a)) occurs when node <I>w</I>, the sibling of node <I>x</I>, is red. Since <I>w</I> must have black children, we can switch the colors of <I>w</I> and <I>p</I>[<I>x</I>] and then perform a left-rotation on <I>p</I>[<I>x</I>] without violating any of the red-black properties. The new sibling of <I>x</I>, one of <I>w</I>'s children, is now black, and thus we have converted case 1 into case 2, 3, or 4.<P>
Cases 2, 3, and 4 occur when node <I>w</I> is black; they are distinguished by the colors of <I>w</I>'s children. In case 2 (lines 10-11 of RB-<FONT FACE="Courier New" SIZE=2>DELETE</FONT>-<FONT FACE="Courier New" SIZE=2>FIXUP</FONT> and Figure 14.7(b)), both of <I>w</I>'s children are black. Since <I>w</I> is also black, we take one black off both <I>x</I> and <I>w</I>, leaving <I>x</I> with only one black and leaving <I>w</I> red, and add an extra black to <I>p</I>[<I>x</I>]. We then repeat the <B>while</B> loop with <I>p</I>[<I>x</I>] as the new node <I>x</I>. Observe that if we enter case 2 through case 1, the color <I>c</I> of the new node <I>x</I> is red, since the original <I>p</I>[<I>x</I>] was red, and thus the loop terminates when it tests the loop condition.<P>
Case 3 (lines 13-16 and Figure 14.7(c)) occurs when <I>w</I> is black, its left child is red, and its right child is black. We can switch the colors of <I>w</I> and its left child <I>left</I>[<I>w</I>] and then perform a right rotation on <I>w</I> without violating any of the red-black properties. The new sibling <I>w</I> of <I>x</I> is now a black node with a red right child, and thus we have transformed case 3 into case 4. <P>
Case 4 (lines 17-21 and Figure 14.7(d)) occurs when node <I>x</I>'s sibling <I>w</I> is black and <I>w</I>'s right child is red. By making some color changes and performing a left rotation on <I>p</I>[<I>x</I>], we can remove the extra black on <I>x</I> without violating any of the red-black properties. Setting <I>x</I> to be the root causes the <B>while</B> loop to terminate when it tests the loop condition.<P>
<img src="276_a.gif"><P>
<h4><a name="07f0_14e2">Figure 14.7 The cases in the while loop of the procedure RB-<FONT FACE="Courier New" SIZE=3><FONT FACE="Courier New" SIZE=1>DELETE</FONT></FONT>. Darkened nodes are black, heavily shaded nodes are red, and lightly shaded nodes, which may be either red or black, are represented by c and c'. The letters <img src="../images/alpha12.gif">, <img src="../images/beta14.gif">, . . ., <img src="../images/zeta12.gif"> represent arbitrary subtrees. In each case, the configuration on the left is transformed into the configuration on the right by changing some colors and/or performing a rotation. A node pointed to by x has an extra black. The only case that causes the loop to repeat is case 2. (a) Case I is transformed to case 2, 3, or 4 by exchanging the colors of nodes B and D and performing a left rotation. (b) In case 2, the extra black represented by the pointer x is moved up the tree by coloring node D red and setting x to point to node B. If we enter case 2 through case 1, the while loop terminates, since the color c is red. (c) Case 3 is transformed to case 4 by exchanging the colors of nodes C and D and performing a right rotation. (d) In case 4, the extra black represented by x can be removed by changing some colors and performing a left rotation (without violating the red-black properties), and the loop terminates.<a name="07f0_14e2"></sub></sup></h4><P>
What is the running time of RB-<FONT FACE="Courier New" SIZE=2>DELETE</FONT>? Since the height of a red-black tree of <I>n</I> nodes is <I>O</I>(lg <I>n</I>), the total cost of the procedure without the call to RB-<FONT FACE="Courier New" SIZE=2>DELETE</FONT>-<FONT FACE="Courier New" SIZE=2>FIXUP</FONT> takes <I>O</I>(lg <I>n</I>) time. Within RB-<FONT FACE="Courier New" SIZE=2>DELETE</FONT>-<FONT FACE="Courier New" SIZE=2>FIXUP</FONT>, cases 1, 3, and 4 each terminate after performing a constant number of color changes and at most three rotations. Case 2 is the only case in which the <B>while</B> loop can be repeated, and then the pointer <I>x</I> moves up the tree at most <I>O</I>(lg <I>n</I>) times and no rotations are performed. Thus, the procedure RB-<FONT FACE="Courier New" SIZE=2>DELETE</FONT>-<FONT FACE="Courier New" SIZE=2>FIXUP</FONT> takes <I>O</I>(lg <I>n</I>) time and performs at most three rotations, and the overall time for RB-<FONT FACE="Courier New" SIZE=2>DELETE</FONT> is therefore also <I>O</I>(lg <I>n</I>).<P>







<h2><a name="07f1_14e3">Exercises<a name="07f1_14e3"></h2><P>