algorithmdata-structurestreered-black-treetree-balancing

Red black tree deletion unknown behaviour

I entered several numbers to a red black tree. (41; 38; 31; 12; 19; 8) after deleting 8 and 12 (1st screenshot) it got into the type of the second screenshot. I can't understand why that 31 turn into red . Please help me with that ? If you could please mention the case related to that. Thank you !

Solution

  • If you check the explanation of the removal algorithm on Wikipedia, you can map their naming of nodes to your tree as follows:

    M = 0012, the black node to remove
    C = a NIL leaf below 0012 (NILs are always considered to be black)

    The article goes on to say about your actual case:

    The complex case is when both M and C are black. [...] We begin by replacing M with its child C. [...] We will relabel this child C (in its new position) N, and its sibling (its new parent's other child) S [...] we will also use P for N's new parent, SL for S's left child, and SR for S's right child

    So now we have after the removal, but before re-colouring:

    enter image description here

    P = 0019 (red)
    N = a NIL leaf, the left child of 0019
    S = 0031, the right child of 0019

    The description identifies several cases, and the case at hand is the following one:

    Case 4: S and S's children are black, but P is red. In this case, we simply exchange the colors of S and P.

    The reason for this colour swap is explained:

    This does not affect the number of black nodes on paths going through S, but it does add one to the number of black nodes on paths going through N, making up for the deleted black node on those paths.

    Recall that in Red Black trees this invariant must be maintained (property 5):

    Every path from a given node to any of its descendant NIL nodes contains the same number of black nodes.

    This invariant would have been violated if the above colour-swap were omitted.