and black and their parent red (unless is the rootin which caseit is colored blackit is possible thatafter such recoloringthe double red problem reappearsalbeit higher up in the tree tsince may have red parent if the double red problem reappears at uthen we repeat the consideration of the two cases at thusa recoloring either eliminates the double red problem at node zor 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 tthat isno more than log( by proposition figure recoloring to remedy the double red problem(abefore recoloring and the corresponding -node in the associated ( , tree before the split(bafter the recoloring (and corresponding nodes in the associated ( , tree after the split