Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 52
Текст из файла (страница 52)
If there is a violation of property 4, it occurs becauseboth z and p[z] are red.Part (c), which deals with violations of red-black properties, is more central to showing thatRB-INSERT-FIXUP restores the red-black properties than parts (a) and (b), which we usealong the way to understand situations in the code. Because we will be focusing on node z andnodes near it in the tree, it is helpful to know from part (a) that z is red. We shall use part (b)to show that the node p[p[z]] exists when we reference it in lines 2, 3, 7, 8, 13, and 14.Recall that we need to show that a loop invariant is true prior to the first iteration of the loop,that each iteration maintains the loop invariant, and that the loop invariant gives us a usefulproperty at loop termination.We start with the initialization and termination arguments.
Then, as we examine how the bodyof the loop works in more detail, we shall argue that the loop maintains the invariant uponeach iteration. Along the way, we will also demonstrate that there are two possible outcomesof each iteration of the loop: the pointer z moves up the tree, or some rotations are performedand the loop terminates.•Initialization: Prior to the first iteration of the loop, we started with a red-black treewith no violations, and we added a red node z.
We show that each part of the invariantholds at the time RB-INSERT-FIXUP is called:a. When RB-INSERT-FIXUP is called, z is the red node that was added.b. If p[z] is the root, then p[z] started out black and did not change prior to thecall of RB-INSERT-FIXUP.c. We have already seen that properties 1, 3, and 5 hold when RB-INSERTFIXUP is called.If there is a violation of property 2, then the red root must be the newly addednode z, which is the only internal node in the tree. Because the parent and bothchildren of z are the sentinel, which is black, there is not also a violation ofproperty 4.
Thus, this violation of property 2 is the only violation of red-blackproperties in the entire tree.If there is a violation of property 4, then because the children of node z areblack sentinels and the tree had no other violations prior to z being added, theviolation must be because both z and p[z] are red. Moreover, there are no otherviolations of red-black properties.••Termination: When the loop terminates, it does so because p[z] is black. (If z is theroot, then p[z] is the sentinel nil[T], which is black.) Thus, there is no violation ofproperty 4 at loop termination.
By the loop invariant, the only property that might failto hold is property 2. Line 16 restores this property, too, so that when RB-INSERTFIXUP terminates, all the red-black properties hold.Maintenance: There are actually six cases to consider in the while loop, but three ofthem are symmetric to the other three, depending on whether z's parent p[z] is a leftchild or a right child of z's grandparent p[p[z]], which is determined in line 2. We havegiven the code only for the situation in which p[z] is a left child.
The node p[p[z]]exists, since by part (b) of the loop invariant, if p[z] is the root, then p[z] is black.Since we enter a loop iteration only if p[z] is red, we know that p[z] cannot be the root.Hence, p[p[z]] exists.Case 1 is distinguished from cases 2 and 3 by the color of z's parent's sibling, or"uncle." Line 3 makes y point to z's uncle right[p[p[z]]], and a test is made in line 4. Ify is red, then case 1 is executed.
Otherwise, control passes to cases 2 and 3. In all threecases, z's grandparent p[p[z]] is black, since its parent p[z] is red, and property 4 isviolated only between z and p[z].Case 1: z's uncle y is redFigure 13.5 shows the situation for case 1 (lines 5–8). Case 1 is executed when both p[z] and yare red. Since p[p[z]] is black, we can color both p[z] and y black, thereby fixing the problemof z and p[z] both being red, and color p[p[z]] red, thereby maintaining property 5. We thenrepeat the while loop with p[p[z]] as the new node z.
The pointer z moves up two levels in thetree.Figure 13.5: Case 1 of the procedure RB-INSERT. Property 4 is violated, since z and itsparent p[z] are both red. The same action is taken whether (a) z is a right child or (b) z is a leftchild. Each of the subtrees α, β, γ, δ, and ε has a black root, and each has the same blackheight. The code for case 1 changes the colors of some nodes, preserving property 5: alldownward paths from a node to a leaf have the same number of blacks. The while loopcontinues with node z's grandparent p[p[z]] as the new z. Any violation of property 4 can nowoccur only between the new z, which is red, and its parent, if it is red as well.Now we show that case 1 maintains the loop invariant at the start of the next iteration.
We usez to denote node z in the current iteration, and z′ p[p[z]] to denote the node z at the test in line1 upon the next iteration.a. Because this iteration colors p[p[z]] red, node z′ is red at the start of the next iteration.b. The node p[z′] is p[p[p[z]]] in this iteration, and the color of this node does not change.If this node is the root, it was black prior to this iteration, and it remains black at thestart of the next iteration.c.
We have already argued that case 1 maintains property 5, and it clearly does notintroduce a violation of properties 1 or 3.If node z′ is the root at the start of the next iteration, then case 1 corrected the loneviolation of property 4 in this iteration. Since z′ is red and it is the root, property 2becomes the only one that is violated, and this violation is due to z′.If node z′ is not the root at the start of the next iteration, then case 1 has not created aviolation of property 2. Case 1 corrected the lone violation of property 4 that existed atthe start of this iteration.
It then made z′ red and left p[z′] alone. If p[z′] was black,there is no violation of property 4. If p[z′] was red, coloring z′ red created oneviolation of property 4 between z′ and p[z′].Case 2: z's uncle y is black and z is a right childCase 3: z's uncle y is black and z is a left childIn cases 2 and 3, the color of z's uncle y is black.
The two cases are distinguished by whether zis a right or left child of p[z]. Lines 10–11 constitute case 2, which is shown in Figure 13.6together with case 3. In case 2, node z is a right child of its parent. We immediately use a leftrotation to transform the situation into case 3 (lines 12–14), in which node z is a left child.Because both z and p[z] are red, the rotation affects neither the black-height of nodes norproperty 5.
Whether we enter case 3 directly or through case 2, z's uncle y is black, sinceotherwise we would have executed case 1. Additionally, the node p[p[z]] exists, since we haveargued that this node existed at the time that lines 2 and 3 were executed, and after moving zup one level in line 10 and then down one level in line 11, the identity of p[p[z]] remainsunchanged. In case 3, we execute some color changes and a right rotation, which preserveproperty 5, and then, since we no longer have two red nodes in a row, we are done. The bodyof the while loop is not executed another time, since p[z] is now black.Figure 13.6: Cases 2 and 3 of the procedure RB-INSERT.
As in case 1, property 4 is violatedin either case 2 or case 3 because z and its parent p[z] are both red. Each of the subtrees α, β,γ, and δ has a black root (α, β, and γ from property 4, and δ because otherwise we would be incase 1), and each has the same black-height. Case 2 is transformed into case 3 by a leftrotation, which preserves property 5: all downward paths from a node to a leaf have the samenumber of blacks. Case 3 causes some color changes and a right rotation, which also preserveproperty 5.
The while loop then terminates, because property 4 is satisfied: there are no longertwo red nodes in a row.Now we show that cases 2 and 3 maintain the loop invariant. (As we have just argued, p[z]will be black upon the next test in line 1, and the loop body will not execute again.)a. Case 2 makes z point to p[z], which is red. No further change to z or its color occurs incases 2 and 3.b.
Case 3 makes p[z] black, so that if p[z] is the root at the start of the next iteration, it isblack.c. As in case 1, properties 1, 3, and 5 are maintained in cases 2 and 3.Since node z is not the root in cases 2 and 3, we know that there is no violation ofproperty 2. Cases 2 and 3 do not introduce a violation of property 2, since the onlynode that is made red becomes a child of a black node by the rotation in case 3.Cases 2 and 3 correct the lone violation of property 4, and they do not intro- duceanother violation.Having shown that each iteration of the loop maintains the invariant, we have shown that RBINSERT-FIXUP correctly restores the red-black properties.AnalysisWhat is the running time of RB-INSERT? Since the height of a red-black tree on n nodes isO(lg n), lines 1–16 of RB-INSERT take O(lg n) time.
In RB-INSERT- FIXUP, the while looprepeats only if case 1 is executed, and then the pointer z moves two levels up the tree. Thetotal number of times the while loop can be executed is therefore O(lg n). Thus, RB-INSERTtakes a total of O(lg n) time. Interestingly, it never performs more than two rotations, since thewhile loop terminates if case 2 or case 3 is executed.Exercises 13.3-1In line 16 of RB-INSERT, we set the color of the newly inserted node z to red. Notice that ifwe had chosen to set z's color to black, then property 4 of a red-black tree would not beviolated. Why didn't we choose to set z's color to black?Exercises 13.3-2Show the red-black trees that result after successively inserting the keys 41, 38, 31, 12, 19, 8into an initially empty red-black tree.Exercises 13.3-3Suppose that the black-height of each of the subtrees α, β, γ, δ, ε in Figures 13.5 and 13.6 is k.Label each node in each figure with its black-height to verify that property 5 is preserved bythe indicated transformation.Exercises 13.3-4Professor Teach is concerned that RB-INSERT-FIXUP might set color[nil[T]] to RED, inwhich case the test in line 1 would not cause the loop to terminate when z is the root.
Showthat the professor's concern is unfounded by arguing that RB-INSERT-FIXUP never setscolor[nil[T]] to RED.Exercises 13.3-5Consider a red-black tree formed by inserting n nodes with RB-INSERT. Argue that if n > 1,the tree has at least one red node.Exercises 13.3-6Suggest how to implement RB-INSERT efficiently if the representation for red-black treesincludes no storage for parent pointers.[1]Case 2 falls through into case 3, and so these two cases are not mutually exclusive.13.4 DeletionLike the other basic operations on an n-node red-black tree, deletion of a node takes time O(lgn). Deleting a node from a red-black tree is only slightly more complicated than inserting anode.The procedure RB-DELETE is a minor modification of the TREE-DELETE procedure(Section 12.3). After splicing out a node, it calls an auxiliary procedure RB-DELETE-FIXUPthat changes colors and performs rotations to restore the red-black properties.RB-DELETE(T, z)1 if left[z] = nil[T] or right[z] = nil[T]2then y ← z3else y ← TREE-SUCCESSOR(z)4 if left[y] ≠ nil[T]5then x ← left[y]6else x ← right[y]7 p[x] ← p[y]8 if p[y] = nil[T]9then root[T] ← x10else if y = left[p[y]]11then left[p[y]] ← x12else right[p[y]] ← x13 if y 3≠ z14then key[z] ← key[y]15copy y's satellite data into z16 if color[y] = BLACK17then RB-DELETE-FIXUP(T, x)18 return yThere are three differences between the procedures TREE-DELETE and RB-DELETE.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
