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 amountthat isby thusrule isn' violated either finallyjust insert it once 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 last for an ordinary binary search tree howeverthat' not the end of the story rotations once 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 figure handed variations of node being inserted 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 gor it' right child of and is right child of converselyx is an inside grandchild if it' on the opposite side of its parent that is of its parent if is an outside grandchildit may be either the left or right child of pdepending on whether is the left or right child of two similar possibilities exist if is an inside grandchild it' these four situations that are shown in figure this multiplicity of what we might call "handed(left or rightvariations is one reason the red-black insertion routine is challenging to program the action we take to restore the red-black rules is determined by the colors and configuration of and its relatives perhaps surprisinglythere are only three major ways in which nodes can be arranged (not counting the handed variations already mentionedeach possibility must be dealt with in different way to preserve red-black correctness and thereby lead to balanced tree we'll list the three possibilities brieflythen discuss each one in detail in its own section figure shows what they look like remember that is always red