chap14.htm

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

<h1><a name="07ec_14d6">14.2 Rotations<a name="07ec_14d6"></h1><P>
<a name="07ec_14d2"><a name="07ec_14d3">The search-tree operations <FONT FACE="Courier New" SIZE=2>TREE</FONT>-<FONT FACE="Courier New" SIZE=2>INSERT</FONT> and <FONT FACE="Courier New" SIZE=2>TREE</FONT>-<FONT FACE="Courier New" SIZE=2>DELETE</FONT>, when run on a red-black tree with <I>n</I> keys, take <I>O</I>(lg <I>n</I>) time. Because they modify the tree, the result may violate the red-black properties enumerated in Section 14.1. To restore these properties, we must change the colors of some of the nodes in the tree and also change the pointer structure.<P>
<img src="266_a.gif"><P>
<h4><a name="07ec_14d7">Figure 14.2 The rotation operations on a binary search tree. The operation <FONT FACE="Courier New" SIZE=2>RIGHT<FONT FACE="Times New Roman" SIZE=2>-<FONT FACE="Courier New" SIZE=2>ROTATE</FONT></FONT></FONT>(T,x) transforms the configuration of the two nodes on the left into the configuration on the right by changing a constant number of pointers. The configuration on the right can be transformed into the configuration on the left by the inverse operation <FONT FACE="Courier New" SIZE=2>LEFT<FONT FACE="Times New Roman" SIZE=2>-<FONT FACE="Courier New" SIZE=2>ROTATE</FONT></FONT></FONT>(T,y). The two nodes might occur anywhere in a binary search tree. The letters <img src="../images/alpha12.gif">, <img src="../images/beta14.gif">, and <img src="../images/gamma14.gif"> represent arbitrary subtrees. A rotation operation preserves the inorder ordering of keys: the keys in <img src="../images/alpha12.gif"> precede key[x], which precedes the keys in <img src="../images/beta14.gif">, which precede key[y], which precedes the keys in <img src="../images/gamma14.gif">.<a name="07ec_14d7"></sub></sup></h4><P>
We change the pointer structure through <I><B>rotation</I></B>, which is a local operation in a search tree that preserves the inorder key ordering. Figure 14.2 shows the two kinds of rotations: left rotations and right rotations. When we do a left rotation on a node <I>x</I>, we assume that its right child <I>y</I> is non-<FONT FACE="Courier New" SIZE=2>NIL</FONT>. The left rotation &quot;pivots&quot; around the link from <I>x</I> to <I>y</I>. It makes <I>y</I> the new root of the subtree, with <I>x</I> as <I>y</I>'s left child and <I>y</I>'s left child as <I>x</I>'s right child.<P>
<a name="07ec_14d4">The pseudocode for <FONT FACE="Courier New" SIZE=2>LEFT</FONT>-<FONT FACE="Courier New" SIZE=2>ROTATE</FONT> assumes that <I>right</I>[<I>x</I>] <img src="../images/noteq.gif"> <FONT FACE="Courier New" SIZE=2>NIL</FONT>.<P>
<img src="266_b.gif"><P>
<a name="07ec_14d5">Figure 14.3 shows how <FONT FACE="Courier New" SIZE=2>LEFT</FONT>-<FONT FACE="Courier New" SIZE=2>ROTATE</FONT> operates. The code for <FONT FACE="Courier New" SIZE=2>RIGHT</FONT>-<FONT FACE="Courier New" SIZE=2>ROTATE</FONT> is similar. Both <FONT FACE="Courier New" SIZE=2>LEFT</FONT>-<FONT FACE="Courier New" SIZE=2>ROTATE</FONT> and <FONT FACE="Courier New" SIZE=2>RIGHT</FONT>-<FONT FACE="Courier New" SIZE=2>ROTATE</FONT> run in <I>O</I>(l) time. Only pointers are changed by a rotation; all other fields in a node remain the same.<P>
<img src="267_a.gif"><P>
<h4><a name="07ec_14d8">Figure 14.3 An example of how the procedure <FONT FACE="Courier New" SIZE=2>LEFT<FONT FACE="Times New Roman" SIZE=2>-<FONT FACE="Courier New" SIZE=2>ROTATE</FONT></FONT></FONT>(T,x) modifies a binary search tree. The <FONT FACE="Courier New" SIZE=2>NIL</FONT> leaves are omitted. Inorder tree walks of the input tree and the modified tree produce the same listing of key values.<a name="07ec_14d8"></sub></sup></h4><P>







<h2><a name="07ed_14d7">Exercises<a name="07ed_14d7"></h2><P>
<a name="07ed_14d8">14.2-1<a name="07ed_14d8"><P>
Draw the red-black tree that results after <FONT FACE="Courier New" SIZE=2>TREE</FONT>-<FONT FACE="Courier New" SIZE=2>INSERT</FONT> is called on the tree in Figure 14.1 with key 36. If the inserted node is colored red, is the resulting tree a red-black tree? What if it is colored black?<P>
<a name="07ed_14d9">14.2-2<a name="07ed_14d9"><P>
Write pseudocode for <FONT FACE="Courier New" SIZE=2>RIGHT</FONT>-<FONT FACE="Courier New" SIZE=2>ROTATE</FONT>.<P>
<a name="07ed_14da">14.2-3<a name="07ed_14da"><P>
Argue that rotation preserves the inorder key ordering of a binary tree.<P>
<a name="07ed_14db">14.2-4<a name="07ed_14db"><P>
<a name="07ed_14d6">Let <I>a, b</I>, and <I>c</I> be arbitrary nodes in subtrees <img src="../images/alpha12.gif"><I>, <img src="../images/beta14.gif"></I>, and <img src="../images/gamma14.gif"><I></I>, respectively, in the left tree of Figure 14.2. How do the depths of <I>a, b</I>, and <I>c</I> change when a left rotation is performed on node <I>x</I> in the figure?<P>
<a name="07ed_14dc">14.2-5<a name="07ed_14dc"><P>
Show that any arbitrary <I>n</I>-node tree can be transformed into any other arbitrary <I>n</I>-node tree using <I>O</I>(<I>n</I>) rotations. (<I>Hint</I>: First show that at most <I>n</I> -1 right rotations suffice to transform any tree into a right-going chain.)<P>
<P>


<P>









<h1><a name="07ee_14db">14.3 Insertion<a name="07ee_14db"></h1><P>
<a name="07ee_14d7"><a name="07ee_14d8"><a name="07ee_14d9"><a name="07ee_14da">Insertion of a node into an <I>n</I>-node red-black tree can be accomplished in <I>O</I>(lg <I>n</I>) time. We use the <FONT FACE="Courier New" SIZE=2>TREE</FONT>-<FONT FACE="Courier New" SIZE=2>INSERT</FONT> procedure (Section 13.3) to insert node <I>x</I> into the tree <I>T</I> as if it were an ordinary binary search tree, and then we color <I>x</I> red. To guarantee that the red-black properties are preserved, we then fix up the modified tree by recoloring nodes and performing rotations. Most of the code for RB-<FONT FACE="Courier New" SIZE=2>INSERT</FONT> handles the various cases that can arise as we fix up the modified tree.<P>
<img src="268_a.gif"><P>
The code for RB-<FONT FACE="Courier New" SIZE=2>INSERT</FONT> is less imposing than it looks. We shall break our examination of the code into three major steps. First, we shall determine what violations of the red-black properties are introduced in lines 1-2 when the node <I>x</I> is inserted and colored red. Second, we shall examine the overall goal of the <B>while</B> loop in lines 3-17. Finally, we shall explore each of the three cases into which the <B>while</B> loop is broken and see how they accomplish the goal. Figure 14.4 shows how RB-<FONT FACE="Courier New" SIZE=2>INSERT</FONT> operates on a sample red-black tree.<P>
Which of the red-black properties can be violated after lines 1-2? Property 1 certainly continues to hold, as does property 2, since the newly inserted red node has <FONT FACE="Courier New" SIZE=2>NIL'S</FONT> for children. Property 4, which says that the number of blacks is the same on every path from a given node, is satisfied as well, because node <I>x</I> replaces a (black) <FONT FACE="Courier New" SIZE=2>NIL</FONT>, and node <I>x</I> is red with <FONT FACE="Courier New" SIZE=2>NIL</FONT> children. Thus, the only property that might be violated is property 3 which says that a red node cannot have a red child. Specifically, property 3 is violated if <I>x</I><FONT FACE="CG Times (W1)" SIZE=2>'</FONT>s parent is red, since <I>x</I> is itself colored red in line 2. Figure 14.4(a) shows such a violation after the node <I>x</I> has been inserted.<P>
<img src="269_a.gif"><P>
<h4><a name="07ee_14dc">Figure 14.4 The operation of RB-<FONT FACE="Courier New" SIZE=2>INSERT</FONT>. (a) A node x after insertion. Since x and its parent p[x] are both red, a violation of property 3 occurs. Since x's uncle y is red, case 1 in the code can be applied. Nodes are recolored and the pointer x is moved up the tree, resulting in the tree shown in (b). Once again, x and its parent are both red, but x's uncle y is black. Since x is the right child of p[x], case 2 can be applied. A left rotation is performed, and the tree that results is shown in (c). Now x is the left child of its parent, and case 3 can be applied. A right rotation yields the tree in (d), which is a legal red-black tree.<a name="07ee_14dc"></sub></sup></h4><P>
The goal of the <B>while</B> loop in lines 3-17 is to move the one violation of property 3 up the tree while maintaining property 4 as an invariant. At the beginning of each iteration of the loop, <I>x</I> points to a red node with a red parent--the only violation in the tree. There are two possible outcomes of each iteration of the loop: the pointer <I>x</I> moves up the tree, or some rotations are performed and the loop terminates.<P>
There are actually six cases to consider in the <B>while</B> loop, but three of them are symmetric to the other three, depending on whether <I>x</I><FONT FACE="CG Times (W1)" SIZE=2>'</FONT>s parent <I>p</I>[<I>x</I>] is a left child or a right child of <I>x</I><FONT FACE="CG Times (W1)" SIZE=2>'</FONT>s grandparent <I>p</I>[<I>p</I>[<I>x</I>]]<I>,</I> which is determined in line 4. We have given the code only for the situation in which <I>p</I>[<I>x</I>] is a left child. We have made the important assumption that the root of the tree is black--a property we guarantee in line 18 each time we terminate--so that <I>p</I>[<I>x</I>] is not the root and <I>p</I>[<I>p</I>[<I>x</I>]] exists.<P>
Case 1 is distinguished from cases 2 and 3 by the color of <I>x'</I>s parent's sibling, or &quot;uncle.&quot; Line 5 makes <I>y</I> point to <I>x</I>'s uncle <I>right</I> [<I>p</I>[<I>p</I>[<I>x</I>]]], and a test is made in line 6. If <I>y</I> is red, then case 1 is executed. Otherwise, control passes to cases 2 and 3. In all three cases, <I>x</I>'s grandparent <I>p</I>[<I>p</I>[<I>x</I>]] is black, since its parent <I>p</I>[<I>x</I>] is red, and property 3 is violated only between <I>x</I> and <I>p</I>[<I>x</I>]<I>.</I><P>
The situation for case 1 (lines 7-10) is shown in Figure 14.5. Case 1 is executed when both <I>p</I>[<I>x</I>] and <I>y</I> are red. Since <I>p</I>[<I>p</I>[<I>x</I>]] is black, we can color both <I>p</I>[<I>x</I>] and <I>y</I> black, thereby fixing the problem of <I>x</I> and <I>p</I>[<I>x</I>] both being red, and color <I>p</I>[<I>p</I>[<I>x</I>]] red, thereby maintaining property 4. The only problem that might arise is that <I>p</I>[<I>p</I>[<I>x</I>]] might have a red parent; hence, we must repeat the <B>while</B> loop with <I>p</I>[<I>p</I>[<I>x</I>]] as the new node <I>x</I>.<P>
In cases 2 and 3, the color of <I>x</I>'s uncle <I>y</I> is black. The two cases are distinguished by whether <I>x</I> is a right or left child of <I>p</I>[<I>x</I>]<I>.</I> Lines 12-13 constitute case 2, which is shown in Figure 14.6 together with case 3. In case 2, node <I>x</I> is a right child of its parent. We immediately use a left rotation to transform the situation into case 3 (lines 14-16), in which node <I>x</I> is a left child. Because both <I>x</I> and <I>p</I>[<I>x</I>] are red, the rotation affects neither the black-height of nodes nor property 4. Whether we enter case 3 directly or through case 2, <I>x'</I>s uncle <I>y</I> is black, since otherwise we would have executed case 1. We execute some color changes and a right rotation, which preserve property 4, and then, since we no longer have two red nodes in a row, we are done. The body of the <B>while</B> loop is not executed another time, since <I>p</I>[<I>x</I>] is now black.<P>
What is the running time of RB-<FONT FACE="Courier New" SIZE=2>INSERT</FONT>? Since the height of a red-black tree on <I>n</I> nodes is <I>O(</I>lg <I>n),</I> the call to <FONT FACE="Courier New" SIZE=2>TREE</FONT>-<FONT FACE="Courier New" SIZE=2>INSERT</FONT> takes <I>O(</I>lg <I>n</I>)<I> </I>time. The <B>while</B> loop only repeats if case 1 is executed, and then the pointer <I>x</I> moves up the tree. The total number of times the <B>while</B> loop can be executed is therefore <I>O(</I>lg <I>n)</I>. Thus, RB-<FONT FACE="Courier New" SIZE=2>INSERT</FONT> takes a total of <I>O</I>(lg <I>n</I>) time. Interestingly, it never performs more than two rotations, since the <B>while</B> loop terminates if case 2 or case 3 is executed.<P>
<img src="271_a.gif"><P>
<h4><a name="07ee_14dd">Figure 14.5 Case 1 of the procedure RB-<FONT FACE="Courier New" SIZE=2>INSERT</FONT>. Property 3 is violated, since x and its parent p[x] are both red. The same action is taken whether (a) x is a right child or (b) x is a left child. Each of the subtrees <FONT FACE="Courier New" SIZE=2><img src="../images/alpha12.gif">, <img src="../images/beta14.gif">, <img src="../images/gamma14.gif">, <img src="../images/delta12.gif"><FONT FACE="Times New Roman" SIZE=2> </FONT></FONT>and <FONT FACE="Courier New" SIZE=2><img src="../images/epsilon.gif"><FONT FACE="Times New Roman" SIZE=2></FONT></FONT> has a black root, and each has the same black-height. The code for case 1 changes the colors of some nodes, preserving property 4: all downward paths from a node to a leaf have the same number of blacks. The while loop continues with node x's grandparent p[p[x]] as the new x. Any violation of property 3 can now occur only between the new x, which is red, and its parent, if it is red as well.<a name="07ee_14dd"></sub></sup></h4><P>
<img src="271_b.gif"><P>
<h4><a name="07ee_14de">Figure 14.6 Cases 2 and 3 of the procedure RB-<FONT FACE="Courier New" SIZE=2>INSERT</FONT>. As in case 1, property 3 is violated in either case 2 or case 3 because x and its parent p[x] are both red. Each of the subtrees <FONT FACE="Courier New" SIZE=2><img src="../images/alpha12.gif">, <img src="../images/beta14.gif">, <img src="../images/gamma14.gif">, <FONT FACE="Times New Roman" SIZE=2></FONT></FONT>and <FONT FACE="Courier New" SIZE=2><img src="../images/delta12.gif"> </FONT>has a black root, and each has the same black-height. Case 2 is transformed into case 3 by a left rotation, which preserves property 4: all downward paths from a node to a leaf have the same number of blacks. Case 3 causes some color changes and a right rotation, which also preserve property 4. The while loop then terminates, because property 3 is satisfied: there are no longer two red nodes in a row.<a name="07ee_14de"></sub></sup></h4><P>







<h2><a name="07ef_0001">Exercises<a name="07ef_0001"></h2><P>
<a name="07ef_0002">14.3-1<a name="07ef_0002"><P>
In line 2 of RB-<FONT FACE="Courier New" SIZE=2>INSERT</FONT>, we set the color of the newly inserted node <I>x</I> to red. Notice that if we had chosen to set <I>x</I>'s color to black, then property 3 of a red-black tree would not be violated. Why didn<FONT FACE="CG Times (W1)" SIZE=2>'</FONT>t we choose to set <I>x</I><FONT FACE="CG Times (W1)" SIZE=2>'</FONT>s color to black?<P>