case the sibling of is red (see figure in this casethe double red denotes an overflow in the corresponding ( tree to fix the problemwe perform the equivalent of split operation namelywe do recoloringwe color and black and their parent red (unless is the rootin which caseit remains blacknotice that unless is the rootthe portion of any path through the affected part of the tree is incident to exactly one black nodeboth before and after the recoloring thereforethe black depth of the tree is unaffected by the recoloring unless is the rootin which case it is increased by one howeverit is possible that the double-red problem reappears after such recoloringalbeit higher up in the tree since may have red parent if the double-red problem reappears at zthen we repeat the consideration of the two cases at thusa recoloring either eliminates the double-red problem at node xor propagates it to the grandparent of we continue going up performing recolorings until we finally resolve the double-red problem (with either final recoloring or trinode restructuringthusthe number of recolorings caused by an insertion is no more than half the height of tree that iso(log nby proposition (az (bfigure recoloring to remedy the double-red problem(abefore recoloring and the corresponding -node in the associated ( tree before the split(bafter recoloring and the corresponding nodes in the associated ( tree after the split as further examplesfigures and show sequence of insertion operations in red-black tree