case the sibling of is black (or none(see figure in this casethe double red denotes the fact that we have added the new node to corresponding -node of the ( tree effectively creating malformed -node this formation has one red node (ythat is the parent of another red node ( )while we want it to have the two red nodes as siblings instead to fix this problemwe perform trinode restructuring of the trinode restructuring is done by the operation restructure( )which consists of the following steps (see again figure this operation is also discussed in section )take node xits parent yand grandparent zand temporarily relabel them as aband cin left-to-right orderso that aband will be visited in this order by an inorder tree traversal replace the grandparent with the node labeled band make nodes and the children of bkeeping inorder relationships unchanged after performing the restructure(xoperationwe color black and we color and red thusthe restructuring eliminates the double-red problem notice that the portion of any path through the restructured part of the tree is incident to exactly one black nodeboth before and after the trinode restructuring thereforethe black depth of the tree is unaffected (ab (bfigure restructuring red-black tree to remedy double red(athe four configurations for xyand before restructuring(bafter restructuring