case node is red (see figure because is red and theavy has black depth at least must be black and the two subtrees of must each have black root and black depth equal to that of theavy in this casewe perform rotation about and zand then recolor black and red this denotes reorientation of -node in the corresponding ( tree this does not immediately resolve the deficitas the new subtree of is an old subtree of with black root and black height equal to that of the original theavy we reapply the algorithm to resolve the deficit at zknowing that the new child that is the root of theavy is now blackand therefore that either case applies or case applies furthermorethe next application will be the lastbecause case is always terminal and case will be terminal given that is red tlight theavy theavy tlight figure rotation and recoloring about red node and black node zassuming black deficit at this amounts to change of orientation in the corresponding -node of ( tree this operation does not affect the black depth of any paths through this portion of the tree furthermorebecause was originally redthe new subtree of must have black root and must have black height equal to the original theavy thereforea black deficit remains at node after the transformation in figure we show sequence of deletions on red-black tree dashed edge in those figuressuch as to the right of in part ( )represents branch with black deficiency that has not yet been resolved we illustrate case restructuring in parts (cand (dwe illustrate case recoloring in parts ( and (gfinallywe show an example of case rotation between parts (iand ( )concluding with case recoloring in part (