they can follow few simple rules that' what the red-black scheme providesin the form of color coding and the four color rules inserting new node now you have enough background to see how red-black tree' insertion routine uses rotations and the color rules to maintain the tree' balance preview we're going to briefly preview our approach to describing the insertion process don' worry if things aren' completely clear in the previewwe'll discuss things in more detail in moment in the discussion that follows we'll use xpand to designate pattern of related nodes is node that has caused rule violation (sometimes refers to newly inserted nodeand sometimes to the child node when parent and child have red-red conflict is particular node is the parent of is the grandparent of (the parent of pon the way down the tree to find the insertion pointyou perform color flip whenever you find black node with two red children ( violation of rule sometimes the flip causes red-red conflict ( violation of rule call the red child and the red parent the conflict can be fixed with single rotation or double rotationdepending on whether is an outside or inside grandchild of following color flips and rotationsyou continue down to the insertion point and insert the new node after you've inserted the new node xif is black you simply attach the new red node if is redthere are two possibilitiesx can be an outside or inside grandchild of you perform two color changes (we'll see what they are in momentif is an outside grandchildyou perform one rotationand if it' an inside grandchild you perform two this restores the tree to balanced state now we'll recapitulate this preview in more detail we'll divide the discussion into three partsarranged in order of complexity color flips on the way down rotations once the node is inserted rotations on the way down if we were discussing these three parts in strict chronological orderwe' examine part before part howeverit' easier to talk about rotations at the bottom of the tree than in the middleand operations and are encountered more frequently than operation so we'll discuss before color flips on the way down the insertion routine in red-black tree starts off doing essentially the same thing it does