1
$\begingroup$

I don't know why case 4 will resolve the issue of the double black of $x$ described in Introduction to algorithm p.329. I know case 1 is transformed into one of {2,3,4} case, and case 2 re-point $x$ to its parent node so it's approaching the root, and case 3 will be transformed into case 4, but both case {3,4} will not change the pointer $x$, anyway so how case 4 work?

Is it because for paths include $C,E$ there is no difference about the number of blacks while for that about $\alpha,\beta$ an extra black node $B$ is passed?

enter image description here

$\endgroup$
1
$\begingroup$

but both case {3,4} will not change the pointer 𝑥, anyway so how case 4 work?

Let us check case 4. Although the parent pointer of node $x$ is not changed, i.e., the parent node of $x$ is still $B$, the color of $B$ is set to black and node $D$ is lifted to become $B$'s parent with $B$'s original color.

So, going from the graph on the left hand side of case 4 on the image in the question to the graph on the right hand side, we have added that "extra" black node that was supposed to attached to $x$, which is, in your words, an extra black node $B$ is passed for the paths going through $\alpha,\beta$.

Furthermore, for that graph on the right hand side, we can check that all simple paths from the node to descendant leaves that do not pass through $A$ contain the same number of black nodes as before. Since all properties of black-red tree have been restored, case 4 ends the while loop, which ends RB-DELETE-FIXUP$(T, x)$, which ends RB-DELETE$(T, z)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.