13.4 Deletion


Argue that after executing $\text{RB-DELETE-FIXUP}$, the root of the tree must be black.

  • Case 1: transform to 2, 3, 4.
  • Case 2: if terminates, the root of the subtree (the new $x$) is set to black.
  • Case 3: transform to 4.
  • Case 4: the root (the new $x$) is set to black.


Argue that if in $\text{RB-DELETE}$ both $x$ and $x.p$ are red, then property 4 is restored by the call to $\text{RB-DELETE-FIXUP}(T, x)$.

Suppose that both $x$ and $x.p$ are red in $\text{RB-DELETE}$. This can only happen in the else-case of line 9. Since we are deleting from a red-black tree, the other child of y.p which becomes $x$'s sibling in the call to $\text{RB-TRANSPLANT}$ on line 14 must be black, so $x$ is the only child of $x.p$ which is red. The while-loop condition of $\text{RB-DELETE-FIXUP}(T, x)$ is immediately violated so we simply set $x.color = black$, restoring property 4.


In Exercise 13.3-2, you found the red-black tree that results from successively inserting the keys $41, 38, 31, 12, 19, 8$ into an initially empty tree. Now show the red-black trees that result from the successive deletion of the keys in the order $8, 12, 19, 31, 38, 41$.

  • initial:

  • delete $8$:

  • delete $12$:

  • delete $19$:

  • delete $31$:

  • delete $38$:

  • delete $41$:


In which lines of the code for $\text{RB-DELETE-FIXUP}$ might we examine or modify the sentinel $T.nil$?

When the node $y$ in $\text{RB-DELETE}$ has no children, the node $x = T.nil$, so we'll examine the line 2 of $\text{RB-DELETE-FIXUP}$.

When the root node is deleted, $x = T.nil$ and the root at this time is $x$, so the line 23 of $\text{RB-DELETE-FIXUP}$ will draw $x$ to black.


In each of the cases of Figure 13.7, give the count of black nodes from the root of the subtree shown to each of the subtrees $\alpha, \beta, \ldots, \zeta$, and verify that each count remains the same after the transformation. When a node has a $color$ attribute $c$ or $c'$, use the notation $\text{count}(c)$ or $\text{count}(c')$ symbolically in your count.

Our count will include the root (if it is black).

  • Case 1: For each subtree, it is $2$ both before and after.

  • Case 2:

    • For $\alpha$ and $\beta$, it is $1 + \text{count}(c)$ in both cases.
    • For the rest of the subtrees, it is from $2 + \text{count}(c)$ to $1 + \text{count}(c)$.

    This decrease in the count for the other subtreese is handled by then having $x$ represent an additional black.

  • Case 3:

    • For $\epsilon$ and $\zeta$, it is $2+\text{count}(c)$ both before and after.
    • For all the other subtrees, it is $1+\text{count}(c)$ both before and after.
  • Case 4:

    • For $\alpha$ and $\beta$, it is from $1 + \text{count}(c)$ to $2 + \text{count}(c)$.
    • For $\gamma$ and $\delta$, it is $1 + \text{count}(c) + \text{count}(c')$ both before and after.
    • For $\epsilon$ and $\zeta$, it is $1 + \text{count}(c)$ both before and after.

This increase in the count for $\alpha$ and $\beta$ is because $x$ before indicated an extra black.


Professors Skelton and Baron are concerned that at the start of case 1 of $\text{RB-DELETE-FIXUP}$, the node $x.p$ might not be black. If the professors are correct, then lines 5–6 are wrong. Show that $x.p$ must be black at the start of case 1, so that the professors have nothing to worry about.

At the start of case 1 we have set $w$ to be the sibling of $x$. We check on line 4 that $w.color == red$, which means that the parent of $x$ and $w$ cannot be red. Otherwise property 4 is violated. Thus, their concerns are unfounded.


Suppose that a node $x$ is inserted into a red-black tree with $\text{RB-INSERT}$ and then is immediately deleted with $\text{RB-DELETE}$. Is the resulting red-black tree the same as the initial red-black tree? Justify your answer.

No, the red-black tree will not necessarily be the same.

  • Example 1:

    • initial:

    • insert $1$:

    • delete $1$:

  • Example 2:

    • initial:

    • insert $1$:

    • delete $1$: