each -node into two -nodes in red-black tree you perform color flips how are these operations equivalentfigure -node split and color flip in figure - we show -node in tree before it is splitfigure - shows the situation after the split the -node that was the parent of the -node becomes -node in figure - we show the red-black equivalent to the tree in - the dotted line surrounds the equivalent of the -node color flip results in the red-black tree of figure - now nodes and are black and is red thus and its parent form the equivalent of -nodeas shown by the dotted line this is the same -node formed by the node split in figure - thus we see that splitting -node during the insertion process in tree is equivalent to performing color flips during the insertion process in red-black tree -node splits and rotations when -node in tree is transformed into its red-black equivalenttwo arrangements are possibleas we showed earlier in figure - either of the two data items can become the parent depending on which one is chosenthe child will be either left child or right childand the slant of the line connecting parent and child will be either left or right both arrangements are validhoweverthey may not contribute equally to balancing the tree let' look at the situation in slightly larger context figure - shows treeand - and - show two equivalent redblack trees derived from the tree by applying the transformation rules the difference between them is the choice of which of the two data items in the -node to make the parentin is the parentin cit'