to cure the red-red conflictyou must do the same two color changes and two rotations as in possibility change the color of (it' ignore the message that the root must be black change the color of ( rotate with ( as the topin the direction that raises (left in this examplethe result is shown in figure rotate with ( as the topin the direction that raises (right in this examplenow you can insert the color flip changes and to black as you insert it the result is shown in figure this concludes the description of how tree is kept red-black correctand therefore balancedduring the insertion process deletion as you may recallcoding for deletion in an ordinary binary search tree is considerably harder than for insertion the same is true in red-black treesbut in additionthe deletion process isas you might expectcomplicated by the need to restore redblack correctness after the node is removed in factthe deletion process is so complicated that many programmers sidestep it in various ways one approachas with ordinary binary treesis to mark node as deleted without actually deleting it any search routine that finds the node knows not to tell anyone about it this solution works in many situationsespecially if deletions are not common occurrence in any casewe're going to forgo discussion of the deletion process you can refer to appendix "further reading,if you want to pursue it the efficiency of red-black trees like ordinary binary search treesa red-black tree allows for searchinginsertionand deletion in (log ntime search times should be almost the same in the red-black tree as in the ordinary tree because the red-black characteristics of the tree aren' used during searches the only penalty is that the storage required for each node is increased slightly to accommodate the red-black color ( boolean variablemore specificallyaccording to sedgewick (see appendix )in practice search in red-black tree takes about log comparisonsand it can be shown that the search cannot require more than *log comparisons