Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 53
Текст из файла (страница 53)
First,all references to NIL in TREE-DELETE are replaced by references to the sentinel nil[T ] inRB-DELETE. Second, the test for whether x is NIL in line 7 of TREE-DELETE is removed,and the assignment p[x] ← p[y] is performed unconditionally in line 7 of RB-DELETE. Thus,if x is the sentinel nil[T], its parent pointer points to the parent of the spliced-out node y.Third, a call to RB-DELETE-FIXUP is made in lines 16–17 if y is black. If y is red, the redblack properties still hold when y is spliced out, for the following reasons:•••no black-heights in the tree have changed,no red nodes have been made adjacent, andsince y could not have been the root if it was red, the root remains black.The node x passed to RB-DELETE-FIXUP is one of two nodes: either the node that was y'ssole child before y was spliced out if y had a child that was not the sentinel nil[T ], or, if y hadno children, x is the sentinel nil[T ].
In the latter case, the unconditional assignment in line 7guarantees that x's parent is now the node that was previously y's parent, whether x is a keybearing internal node or the sentinel nil[T].We can now examine how the procedure RB-DELETE-FIXUP restores the red-blackproperties to the search tree.RB-DELETE-FIXUP(T, x)1 while x ≠ root[T] and color[x] = BLACK2do if x = left[p[x]]3then w ← right[p[x]]4if color[w] = RED5then color[w] ← BLACK6color[p[x]] ← RED7LEFT-ROTATE(T, p[x])89▹Case 1▹Case 1▹Case 1w ← right[p[x]]▹ Case 1if color[left[w]] = BLACK and color[right[w]] = BLACK10then color[w] ← RED▹Case 21112x p[x]else if color[right[w]] = BLACK▹Case 2▹Case 3▹Case 313then color[left[w]] ← BLACK14color[w] ← RED15RIGHT-ROTATE(T, w)16w ← right[p[x]]▹▹Case 3Case 317color[w] ← color[p[x]]▹Case 418color[p[x]] ← BLACK▹Case 419color[right[w]] ← BLACK20LEFT-ROTATE(T, p[x])21x ← root[T]▹▹▹Case 4Case 4Case 422else (same as then clause with "right" and "left" exchanged)23 color[x] ← BLACKIf the spliced-out node y in RB-DELETE is black, three problems may arise.
First, if y hadbeen the root and a red child of y becomes the new root, we have violated property 2. Second,if both x and p[y] (which is now also p[x]) were red, then we have violated property 4. Third,y's removal causes any path that previously contained y to have one fewer black node.
Thus,property 5 is now violated by any ancestor of y in the tree. We can correct this problem bysaying that node x has an "extra" black. That is, if we add 1 to the count of black nodes on anypath that contains x, then under this interpretation, property 5 holds. When we splice out theblack node y, we "push" its blackness onto its child. The problem is that now node x is neitherred nor black, thereby violating property 1. Instead, node x is either "doubly black" or "redand-black," and it contributes either 2 or 1, respectively, to the count of black nodes on pathscontaining x. The color attribute of x will still be either RED (if x is red-and-black) orBLACK (if x is doubly black). In other words, the extra black on a node is reflected in x'spointing to the node rather than in the color attribute.The procedure RB-DELETE-FIXUP restores properties 1, 2, and 4.
Exercises 13.4-1 and13.4-2 ask you to show that the procedure restores properties 2 and 4, and so in the remainderof this section, we shall focus on property 1. The goal of the while loop in lines 1–22 is tomove the extra black up the tree until1.
x points to a red-and-black node, in which case we color x (singly) black in line 23,2. x points to the root, in which case the extra black can be simply "removed," or3. suitable rotations and recolorings can be performed.Within the while loop, x always points to a nonroot doubly black node. We determine in line2 whether x is a left child or a right child of its parent p[x].
(We have given the code for thesituation in which x is a left child; the situation in which x is a right child—line 22—issymmetric.) We maintain a pointer w to the sibling of x. Since node x is doubly black, node wcannot be nil[T]; otherwise, the number of blacks on the path from p[x] to the (singly black)leaf w would be smaller than the number on the path from p[x] to x.The four cases[2] in the code are illustrated in Figure 13.7. Before examining each case indetail, let's look more generally at how we can verify that the transformation in each of thecases preserves property 5.
The key idea is that in each case the number of black nodes(including x's extra black) from (and including) the root of the subtree shown to each of thesubtrees α, β, ..., ζ is preserved by the transformation. Thus, if property 5 holds prior to thetransformation, it continues to hold afterward. For example, in Figure 13.7(a), whichillustrates case 1, the number of black nodes from the root to either subtree α or β is 3, bothbefore and after the transformation. (Again, remember that node x adds an extra black.)Similarly, the number of black nodes from the root to any of γ, δ, ε, and is ζ, both before andafter the transformation. In Figure 13.7(b), the counting must involve the value c of the colorattribute of the root of the subtree shown, which can be either RED or BLACK.
If we definecount(RED) = 0 and count(BLACK) = 1, then the number of black nodes from the root to α is2 + count(c), both before and after the transformation. In this case, after the transformation,the new node x has color attribute c, but this node is really either red-and-black (if c = RED)or doubly black (if c = BLACK). The other cases can be verified similarly (see Exercise 13.45).Figure 13.7: The cases in the while loop of the procedure RB-DELETE-FIXUP. Darkenednodes have color attributes BLACK, heavily shaded nodes have color attributes RED, andlightly shaded nodes have color attributes represented by c and c′, which may be either REDor BLACK.
The letters α, β, ..., ζ represent arbitrary subtrees. In each case, the configurationon the left is transformed into the configuration on the right by changing some colors and/orperforming a rotation. Any node pointed to by x has an extra black and is either doubly blackor red-and-black. The only case that causes the loop to repeat is case 2. (a) Case 1 istransformed to case 2, 3, or 4 by exchanging the colors of nodes B and D and performing aleft rotation.
(b) In case 2, the extra black represented by the pointer x is moved up the tree bycoloring node D red and setting x to point to node B. If we enter case 2 through case 1, thewhile loop terminates because the new node x is red-and-black, and therefore the value c of itscolor attribute is RED.
(c) Case 3 is transformed to case 4 by exchanging the colors of nodesC and D and performing a right rotation. (d) In Case 4, the extra black represented by x can beremoved by changing some colors and performing a left rotation (without violating the redblack properties), and the loop terminates.Case 1: x's sibling w is redCase 1 (lines 5–8 of RB-DELETE-FIXUP and Figure 13.7(a)) occurs when node w, thesibling of node x, is red. Since w must have black children, we can switch the colors of w andp[x] and then perform a left-rotation on p[x] without violating any of the red-black properties.The new sibling of x, which is one of w's children prior to the rotation, is now black, and thuswe have converted case 1 into case 2, 3, or 4.Cases 2, 3, and 4 occur when node w is black; they are distinguished by the colors of w'schildren.Case 2: x's sibling w is black, and both of w's children are blackIn case 2 (lines 10–11 of RB-DELETE-FIXUP and Figure 13.7(b)), both of w's children areblack.
Since w is also black, we take one black off both x and w, leaving x with only one blackand leaving w red. To compensate for removing one black from x and w, we would like to addan extra black to p[x], which was originally either red or black. We do so by repeating thewhile loop with p[x] as the new node x. Observe that if we enter case 2 through case 1, thenew node x is red-and-black, since the original p[x] was red. Hence, the value c of the colorattribute of the new node x is RED, and the loop terminates when it tests the loop condition.The new node x is then colored (singly) black in line 23.Case 3: x's sibling w is black, w's left child is red, and w's right child is blackCase 3 (lines 13–16 and Figure 13.7(c)) occurs when w is black, its left child is red, and itsright child is black. We can switch the colors of w and its left child left[w] and then perform aright rotation on w without violating any of the red-black properties.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
