data structures using void case (struct node *nstruct node * *gu uncle ( ) grand_parent( )if (( !null&( -colour =red) -parent -colour blacku -colour blackg -colour redcase ( )else insert_case ( )note in the remaining caseswe assume that the parent node is the left child of its parent if it is the right childthen interchange left and right in cases and case the parent is red but the uncle is black and is the right child of and is the left child of in order to fix this problema left rotation is done to switch the roles of the new node and its parent after the rotationnote that in the codewe have re-labelled and and thencase is called to deal with the new node' parent this is done because property which says both children of every red node should be black is still violated figure illustrates case insertion note that in case is the left child of and is the right child of gwe have to perform right rotation in the code that handles case we check for and and thenperform either left or right rotation figure insertion in case void case (struct node *nstruct node * grand_ parent( )if (( = -parent -right&( -parent = -left)rotate_left( -parent) -leftelse if (( = -parent -left&( -parent = -right)rotate_right( -parent) -rightcase ( )case the parent is red but the uncle is black and the new node is the left child of pand is the left child of its parent in order to fix this problema right rotation on (the grandparent of nis performed after this rotationthe former parent is now the parent of both the new node and the former grandparent we know that the colour of is black (because otherwise its former child could not have been red)so now switch the colours of and so that the resulting tree satisfies property which states that both children of red node are black case insertion is illustrated in fig