advanced data structures and implementation figure zig rotation and zig-zag rotation work if is black chain or zig-zag chain (in either of two directionsfigure shows how we can rotate the tree for the case where is left child (note there is symmetric caseeven though is leafwe have drawn more general case that allows to be in the middle of the tree we will use this more general rotation later the first case corresponds to single rotation between and gand the second case corresponds to double rotationfirst between and and then between and when we write the codewe have to keep track of the parentthe grandparentandfor reattachment purposesthe great-grandparent in both casesthe subtree' new root is colored blackand so even if the original great-grandparent was redwe removed the possibility of two consecutive red nodes equally importantthe number of black nodes on the paths into aband has remained unchanged as result of the rotations so far so good but what happens if is redas is the case when we attempt to insert in the tree in figure in that caseinitially there is one black node on the path from the subtree' root to after the rotationthere must still be only one black node but in both casesthere are three nodes (the new rootgand son the path to since only one may be blackand since we cannot have consecutive red nodesit follows that we' have to color both and the subtree' new root redand (and our fourth nodeblack that' greatbut what happens if the great-grandparent is also redin that casewe could percolate this procedure up toward the root as is done for -trees and binary heapsuntil we no longer have two consecutive red nodesor we reach the root (which will be recolored blacktop-down red-black trees implementing the percolation would require maintaining the path using stack or parent links we saw that splay trees are more efficient if we use top-down procedureand it