figures and resolving this case corresponds to fusion operation in the corresponding ( , tree we do recoloringwe color blackwe color redandif is redwe color it black (figure )otherwisewe color double black (figure henceafter this recoloringthe double black problem may reappear at the parent of (see figure that isthis recoloring either eliminates the double black problem or propagates it into the parent of the current node we then repeat consideration of these three cases at the parent thussince case performs trinode restructuring operation and stops (andas we will soon seecase is similar)the number of recolorings caused by removal is no more than log( figure recoloring of red-black tree that fixes the double black problem(abefore the recoloring and corresponding nodes in the associated ( , tree before the fusion (other similar configurations are possible)(bafter the recoloring and corresponding nodes in the associated ( , tree after the fusion