figure color fliponly if ' parent is red do we continue with rotation turns out that we can apply top-down procedure to red-black trees that guarantees that won' be red the procedure is conceptually easy on the way downwhen we see node that has two red childrenwe make red and the two children black (if is the rootafter the color flip it will be red but can be made black immediately to restore property figure shows this color flip this will induce red-black violation only if ' parent is also red but in that casewe can apply the appropriate rotations in figure what if ' parent' sibling is redthis possibility has been removed by our actions on the way downand so ' parent' sibling can' be redspecificallyif on the way down the tree we see node that has two red childrenwe know that ' grandchildren must be blackand that since ' children are made black tooeven after the rotation that may occurwe won' see another red node for two levels thus when we see xif ' parent is redit is not possible for ' parent' sibling to be red also as an examplesuppose we want to insert into the tree in figure on the way down the treewe see node which has two red children thuswe perform color flipmaking redand and black now and are both red we perform the single rotation between and making the black root of ' right subtreeand and both red we then continueperforming an identical action if we see other nodes on the path that contain two red children when we get to the leafwe insert as red nodeand since the parent is blackwe are done the resulting tree is shown in figure as figure showsthe red-black tree that results is frequently very well balanced experiments suggest that the average red-black tree is about as deep as an average avl tree and thatconsequentlythe searching times are typically near optimal the advantage figure insertion of into figure