node should be insertedgoing left or right at each node depending on the relative size of the node' key and the search key howeverin red-black treegetting to the insertion point is complicated by color flips and rotations we introduced color flips in experiment now we'll look at them in more detail imagine the insertion routine proceeding down the treegoing left or right at each nodesearching for the place to insert new node to make sure the color rules aren' brokenit needs to perform color flips when necessary here' the ruleevery time the insertion routine encounters black node that has two red childrenit must change the children to black and the parent to red (unless the parent is the rootwhich always remains blackfigure color flip how does color flip affect the red-black rulesfor conveniencelet' call the node at the top of the trianglethe one that' red before the flipp for parent we'll call ' left and right children and this is shown in figure black heights unchanged figure shows the nodes after the color flip the flip leaves unchanged the number of black nodes on the path from the root on down through to the leaf or null nodes all such paths go through pand then through either or before the fliponly is blackso the triangle (consisting of px and adds one black node to each of these paths after the flipp is no longer blackbut both and areso again the triangle contributes one black node to every path that passes through it so color flip can' cause rule to be violated color flips are helpful because they make red leaf nodes into black leaf nodes this makes it easier to attach new red nodes without violating rule could be two reds 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 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 avoids violating rule does this affect the