At tech-related networking events in New York over the past year, I’ve heard “algorithm” used increasingly in a sense not yet documented in the Oxford English Dictionary: to mean ‘business model’. I suppose this is another result of businesspeople’s indirect exposure to mathematical ideas through the channel most accessible to them: media accounts of money-making lore.
Tag Archives: algorithms
Annotations of Cormen et al.’s algorithm for a Red-Black Tree (delete and delete-fixup functions only)
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, such as RB-TRANSPLANT and 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[end]
