Skip to content

13.4 Deletion

13.4-1

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.

13.4-2

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.

13.4-3

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$:

13.4-4

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

Since it is possible that $w$ is $T.nil$, any line of $\text{RB-DELETE-FIXUP}(T, x)$ which examines or modifies w must be included. However, as described on page 317, $x$ will never be $T.nil$, so we need not include those lines.

13.4-5

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.

13.4-6

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.

Case 1 occurs only if $x$'s sibling $w$ is red. If $x.p$ were red, then there would be two reds in a row, namely $x.p$ (which is also $w.p$) and $w$, and we would have had these two reds in a row even before calling $\text{RB-DELETE}$.

13.4-7

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. Here are two examples: one in which the tree's shape changes, and one in which the shape remains the same but the node colors change.