we must also recolor the nodes we do this before doing any rotations (this order doesn' really matterbut if we wait until after the rotations to recolor the nodesit' hard to know what to call them here are the steps switch the color of ' grandparent ( in this example switch the color of (not its parentx is here rotate with ' parent at the top (not the grandparentthe parent is )in the direction that raises ( left rotation in this example rotate again with ' grandparent ( at the topin the direction that raises ( right rotationthe rotations and recoloring restore the tree to red-black correctness and also balance it (as much as possibleas with possibility there is an analogous case in which is the right child of rather than the left what about other possibilitiesdo the three post-insertion possibilities we just discussed really cover all situationssupposefor examplethat has sibling sthe other child of this scenario might complicate the rotations necessary to insert but if is blackthere' no problem inserting (that' possibility if is redboth its children must be black (to avoid violating rule it can' have single child that' black because the black heights would be different for and the null child howeverwe know is redso we conclude that it' impossible for to have sibling unless is red another possibility is that gthe grandparent of phas child uthe sibling of and the uncle of againthis scenario would complicate any necessary rotations howeverif is blackthere' no need for rotations when inserting xas we've seen so let' assume is red then must also be redotherwisethe black height going from to would be different from that going from to but black parent with two red children is flipped on the way downso this situation can' exist either thusthe three possibilities just discussed are the only ones that can exist (except thatin possibilities and can be right or left child and can be right or left childwhat the color flips accomplished suppose that performing rotation and appropriate color changes caused other violations of the red-black rules to appear further up the tree you can imagine situations in which you would need to work your way all the way back up the treeperforming rotations and color switchesto remove rule violations fortunatelythis situation can' arise using color flips on the way down has eliminated the situations in which rotation could introduce any rule violations further up the tree it ensures that one or two rotations will restore red-black correctness in