red-black trees the entire tree actuallyproving this is beyond the scope of this bookbut such proof is possible the color flips on the way down 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 operation 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 in the discussion of color flips during the insertion processwe noted that color flip can cause violation of rule ( parent and child can' both be redwe also noted that rotation can fix this violation on the way down there are two possibilitiescorresponding to possibility and possibility during the insertion phase described earlier the offending node can be an outside grandchildor it can be an inside grandchild (in the situation corresponding to possibility no action is required outside grandchild firstwe'll examine an example in which the offending node is an outside grandchild by "offending node,we 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 do flipof and its children and you press the flip button the flip is carried outbut now the message says errorparent and child are both redreferring to and its child the resulting tree is shown in figure the procedure used to fix this rule violation is similar to the post-insertion operation with an outside grandchilddescribed earlier we must perform two color switches and one rotation so we can discuss this in the same terms we did when inserting nodewe'll call the node at the top of the triangle that was flipped (which is in this casex this looks little oddbecause we're used to thinking of as the node being insertedand here it' not even leaf node howeverthese on-the-way-down rotations can take place anywhere within the tree the parent of is ( in this case)and the grandparent of --the parent of --is ( in this casewe follow the same set of rules we did under possibility discussed earlier