Deletion in red black tree

Question

I am trying to follow the RB-DELETE-FIXUP in Introduction to Algorithm 3rd edition. They have this code:

RB-DELETE-FIXUP(T, x)
 1 while x != root[T] and color[x] == BLACK
 2     do if x == left[p[x]]
 3           then w = right[p[x]]
 4                if color[w] == RED
 5                   then color[w] = BLACK                        ?  Case 1
 6                        color[p[x]] = RED                       ?  Case 1
 7                        LEFT-ROTATE(T, p[x])                    ?  Case 1
 8                        w = right[p[x]]                         ?  Case 1
 9                if color[left[w]] == BLACK and color[right[w]] == BLACK
10                   then color[w] = RED                          ?  Case 2
11                        x = p[x]                                  ?  Case 2
12                   else if color[right[w]] == BLACK
13                           then color[left[w]] = BLACK          ?  Case 3
14                                color[w] = RED                  ?  Case 3
15                                RIGHT-ROTATE(T, w)              ?  Case 3
16                                w = right[p[x]]                 ?  Case 3
17                         color[w] = color[p[x]]                 ?  Case 4
18                         color[p[x]] = BLACK                    ?  Case 4
19                         color[right[w]] = BLACK                ?  Case 4
20                         LEFT-ROTATE(T, p[x])                   ?  Case 4
21                         x = root[T]                            ?  Case 4
22        else (same as then clause with "right" and "left" exchanged)
23 color[x] = BLACK

I am not able to understand how the tree is being balanced in case 4. Looking at this image: (from here)

The result for case 4 is not balanced. From D to A, the black-color height is 2. And D to E, the black-color height is 1. What am I missing here?

I have no idea and I have been looking at this question for awhile. When I implemented a RB tree, I used wikipedia for reference which has different cases. I'll continue to grind on it and see what I am missing. — Justin

Christopher Barber Christopher Barber · Accepted Answer · 2014-05-30T23:14:55

What you are missing is that the left hand side is not balanced. This routine is called after the parent of x has been spliced out of the tree, and only if the parent was black. Since the tree was balanced prior to removal of the parent, then we know that the subtree rooted at A must have a black height that it is one less than that of the subtree rooted at D. Since E is originally red and D is black, then the subtree rooted at E must originally have the same black height as A. After the transformation, the color of E is now black, so its black height is now one more than A, so the two sides of the tree are indeed balanced.

Deletion in red black tree

1 Answers