red-black trees violation of rule although rule is not violated by color fliprule ( node and its parent can' both be redmay be if the parent of is blackthere' no problem when is changed from black to red howeverif the parent of is redthenafter the color changewe'll have two reds in row this problem needs to be fixed before we continue down the path to insert the new node we can correct the situation with rotationas we'll soon see the root situation what about the rootremember that color flip of the root and its two children leaves the rootas well as its childrenblack this color flip avoids violating rule does this affect the other red-black rulesclearlythere are no red-to-red conflicts because we've made more nodes black and none red thusrule isn' violated alsobecause the root and one or the other of its two children are in every paththe black height of every path is increased the same amount--that isby thusrule isn' violated either finallyjust insert it after you've worked your way down to the appropriate place in the treeperforming color flips (and rotationsif necessary on the way downyou can then insert the new node as described in the preceding for an ordinary binary search tree howeverthat' not the end of the story rotations after the node is inserted the insertion of the new node may cause the red-black rules to be violated thereforefollowing the insertionwe must check for rule violations and take appropriate steps remember thatas described earlierthe newly inserted nodewhich we'll call xis always red may be located in various positions relative to and gas shown in figure remember that node is an outside grandchild if it' on the same side of its parent that is of its parent that isx is an outside grandchild if either it' left child of and is left child of (figure )or it' right child of and is right child of (figure dconverselyx is an inside grandchild if it' on the opposite side of its parent that is of its parent (figures and cthe multiplicity of what we might call "handed(left or rightvariations shown in figure is one reason the red-black insertion routine is so complex to program