13.4 Deletion
13.41¶
Argue that after executing $\text{RBDELETEFIXUP}$, 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.42¶
Argue that if in $\text{RBDELETE}$ both $x$ and $x.p$ are red, then property 4 is restored by the call to $\text{RBDELETEFIXUP}(T, x)$.
Suppose that both $x$ and $x.p$ are red in $\text{RBDELETE}$. This can only happen in the elsecase of line 9. Since we are deleting from a redblack tree, the other child of y.p which becomes $x$'s sibling in the call to $\text{RBTRANSPLANT}$ on line 14 must be black, so $x$ is the only child of $x.p$ which is red. The whileloop condition of $\text{RBDELETEFIXUP}(T, x)$ is immediately violated so we simply set $x.color = black$, restoring property 4.
13.43¶
In Exercise 13.32, you found the redblack tree that results from successively inserting the keys $41, 38, 31, 12, 19, 8$ into an initially empty tree. Now show the redblack 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.44¶
In which lines of the code for $\text{RBDELETEFIXUP}$ might we examine or modify the sentinel $T.nil$?
When the node $y$ in $\text{RBDELETE}$ has no children, the node $x = T.nil$, so we'll examine the line 2 of $\text{RBDELETEFIXUP}$.
When the root node is deleted, $x = T.nil$ and the root at this time is $x$, so the line 23 of $\text{RBDELETEFIXUP}$ will draw $x$ to black.
13.45¶
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.46¶
Professors Skelton and Baron are concerned that at the start of case 1 of $\text{RBDELETEFIXUP}$, 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.
13.47¶
Suppose that a node $x$ is inserted into a redblack tree with $\text{RBINSERT}$ and then is immediately deleted with $\text{RBDELETE}$. Is the resulting redblack tree the same as the initial redblack tree? Justify your answer.
No, the redblack tree will not necessarily be the same.

Example 1:

initial:

insert $1$:

delete $1$:


Example 2:

initial:

insert $1$:

delete $1$:
