we consider three possible cases to remedy deficit case node is black and has red child (see figure we perform trinode restructuringas originally described in section the operation restructure(xtakes the node xits parent yand grandparent zlabels them temporarily left to right as aband cand replaces with the node labeled bmaking it the parent of the other two we color and blackand give the former color of notice that the path to tlight in the result includes one additional black node after the restructurethereby resolving its deficit in contrastthe number of black nodes on paths to any of the other three subtrees illustrated in figure remains unchanged resolving this case corresponds to transfer operation in the ( tree between the two children of the node with the fact that has red child assures us that it represents either -node or -node in effectthe item previously stored at is demoted to become new -node to resolve the deficiencywhile an item stored at or its child is promoted to take the place of the item previously stored at tlight tlight tlight tlight figure resolving black deficit in tlight by performing trinode restructuring as restructure(xtwo possible configurations are shown (two other configurations are symmetricthe gray color of in the left figures denotes the fact that this node may be colored either red or black the root of the restructured portion is given that same colorwhile the children of that node are both colored black in the result