suppose now that we are asked to remove an entry with key from red-black tree removing such an entry initially proceeds as for binary search tree (section firstwe search for node storing such an entry if node does not have an external childwe find the internal node following in the inorder traversal of tmove the entry at to uand perform the removal at thuswe may consider only the removal of an entry with key stored at node with an external child alsoas we did for insertionswe keep in mind the correspondence between red-black tree and its associated ( , tree (and the removal algorithm for 'to remove the entry with key from node of with an external child we proceed as follows let be the sibling of and be the parent of we remove nodes and wand make child of if was red (hence is blackor is red (hence was black)we color black and we are done ifinsteadr is black and was blackthento preserve the depth propertywe give fictitious double black color we now have color violationcalled the double black problem double black in denotes an underflow in the corresponding ( , tree recall that is the parent of the double black node to remedy the double-black problem at rwe consider three cases case the sibling of is black and has red child (see figure resolving this case corresponds to transfer operation in the ( , tree we perform trinode restructuring by means of operation restructure(zrecall that the operation restructure(ztakes the node zits parent yand grandparent xlabels them temporarily left to right as aband cand replaces with the node labeled bmaking it the parent of the other two (see also the description of restructure in section we color and blackgive the former color of xand color black this trinode restructuring eliminates the double black problem henceat most one restructuring is performed in removal operation in this case figure restructuring of red-black tree to remedy the double black problem(aand (bconfigurations before the restructuringwhere is right child and the associated nodes in the corresponding ( , tree before the transfer (two other symmetric configurations where is left child are possible)(cconfiguration after the restructuring and the associated nodes in the corresponding ( , tree after the transfer the grey color for node in parts (