case node is black and both children of are black (or noneresolving this case corresponds to fusion operation in the corresponding ( tree as must represent -node we do recoloringwe color redandif is redwe color it black (see figure this does not introduce any red violationbecause does not have red child in the case that was originally redand thus the parent in the corresponding ( tree is -node or -nodethis recoloring resolves the deficit (see figure the path leading to tlight includes one additional black node in the resultwhile the recoloring did not affect the number of black nodes on the path to the subtrees of theavy in the case that was originally blackand thus the parent in the corresponding ( tree is -nodethe recoloring has not increased the number of black nodes on the path to tlight in factit has reduced the number of black nodes on the path to theavy (see figure after this stepthe two children of will have the same black height howeverthe entire tree rooted at has become deficientthereby propogating the problem higher in the treewe must repeat consideration of all three cases at the parent of as remedy tlight theavy (az tlight theavy tlight (bfigure resolving black deficit in tlight by recoloring operation(awhen is originally redreversing the colors of and resolves the black deficit in tlight ending the process(bwhen is originally blackrecoloring causes the entire subtree of to have black deficitrequiring cascading remedy