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 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 redotherwise the 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 thus the three possibilities discussed above 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 one 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 the entire tree actually proving this is beyond the scope of this bookbut such proof is possible it' the color flips on the way down that make insertion in red-black trees more efficient than in other kinds of balanced treessuch as avl trees they ensure that you need to pass through the tree only onceon the way down rotations on the way down now we'll discuss the last of the three operations involved in inserting nodemaking rotations on the way down to the insertion point as we notedalthough we're discussing this lastit actually takes place before the node is inserted we've waited until now to discuss it only because it was easier to explain rotations for just-installed node than for nodes in the middle of the tree during the discussion of color flips during the insertion processwe noted that it' possible for color flip to cause violation of rule ( parent and child can' both be redwe also noted that rotation can fix this violation there are two possibilitiescorresponding to possibility and possibility during the insertion phase described above the offending node can be an outside grandchild or it can be an inside grandchild (in the situation corresponding to possibility no action is required outside grandchild first we'll examine an example in which the offending node is an outside grandchild by "offending nodewe mean the child in the parent-child pair that caused the red-red conflict start new tree with the nodeand insert the following nodes and you'll need to do color flips when inserting and now try to insert node with the value you'll be told you must flip and its children and you push the flip button the flip is carried outbut now the message says errorparent and child are both redreferring to and its child the