I recently completed a partial implementation in Python of the Red-Black Tree algorithm from Chapter 13 of Introduction to Algorithms, 3rd ed., by Cormen, Leiserson, Rivest, and Stein. In a number of places I found the pseudo-code hard to implement, and devoted considerable time to annotating it. For the benefit of others who may be attempting the same project, I offer my annotations here of the RB-DELETE and RB-DELETE-FIXUP functions, which were the most difficult to follow.
As always, comment and criticism are welcome. For functions not shown,
TREE-MINIMUM, see the book by Cormen et al.
RB-DELETE(T, z) # Identifying Cormen's variable names in this function: # z: node to delete # y: successor node # x: node that moves into y's original position # T: tree object # 1. Retrieve node to be deleted, as "z" (Cormen does not # show this.) # 2. Cormen creates "y" to manipulate subtrees and color # of node 1 y = z # 3. If y is black, must later run RB-DELETE-FIXUP # So store node's color in separate variable # "y-original-color"; y itself cannot be used, # since it may be changed below 2 y-original-color = y.color # 4a. If z has only one subtree, # then replace z with that subtree; # use "x" to manipulate the subtree in interim 3 if z.left == T.nil 4 x = z.right 5 RB-TRANSPLANT(T, z, z.right) 6 elseif z.right == T.nil 7 x = z.left 8 RB-TRANSPLANT(T, z, z.left) # 4b. But if z has two subtrees or none, # must set y to z's successor. # 4bi. Traverse down left subtree to the bottom 9 else y = TREE-MINIMUM(z.right) # 4bii. Reset "y-original-color" based on newly set y 10 y-original-color = y.color # 4biii. Set "x" for successor's right subtree 11 x = y.right # 4biv. y now replaces z # 4biv-a. If we traversed only one level down, # then keep y as parent of x 12 if y.p == z 13 x.p = y # 4biv-b. But if we traversed more than one level down, # then have y adopt z's right child. 14 else RB-TRANSPLANT(T, y, y.right) 15 y.right = z.right 16 y.right.p = y # 4bv. Move left subtree of "z" to "y" 17 RB-TRANSPLANT(T, z, y) 18 y.left = z.left 19 y.left.p = y # 4bvi. Move z's color to y 20 y.color = z.color # 5. Finally, do any "fix-up" that is needed. 21 if y-original-color == BLACK 22 RB-DELETE-FIXUP(T, x) RB-DELETE-FIXUP (T, x) # PRE: x is a black node that has been moved as # successor to a deleted node # POST: red-black properties, disturbed by the deletion, # are restored. # Identifying Cormen's variable names: # x: node in question # w: x's sibling # T: tree object # 1. Do this for a black, non-root node. 1 while x ≠ T.root and x.color == BLACK # 1a. For x as left sibling 2 if x == x.p.left 3 w = x.p.right # 1ai. Case 1. Sibling is red. 4 if w.color == RED # 1ai-a. Make it black and parent red 5 w.color = BLACK 6 x.p.color = RED # 1ai-b. Then left-rotate and recognize the new sibling # to our node 7 LEFT-ROTATE(T, x.p) 8 w = x.p.right # 1aii. Case 2. Sibling's children are both black. 9 if w.left.color == BLACK and w.right.color == BLACK # 1aii-a. Make sibling red and declare parent to be new # node in question (eventually to be made black, # at the end of this function). 10 w.color = RED 11 x = x.p # 1aiii. Case 3. Sibling's right child is black. 12 else if w.right.color == BLACK # 1aiii-a. Sibling's left child must be red; # make it black and make sibling itself red; # then right-rotate sibling; # that finally produces Case 4. 13 w.left.color = BLACK 14 w.color = RED 15 RIGHT-ROTATE(T, w) # 1aiii-b. Recognize new right sibling. 16 w = x.p.right # 1aiv. Case 4. Parent and sibling's right child are red. # NOTE Although Cormen does not add an # "if" test here, I suggest doing so. # 1aiv-a. Sibling adopts parent's color 17 w.color = x.p.color # 1aiv-b. Parent and sibling's right child become black 18 x.p.color = BLACK 19 w.right.color = BLACK # 1aiv-c. Left-rotate. 20 LEFT-ROTATE(T, x.p) # 1aiv-d. End condition non-root, ending initial # while-loop. 21 x = T.root 22 else (same as then clause with “right” and “left” exchanged) # 2. Finally, set node to black, in case it was made red # in Case 2. 23 x.color = BLACK