3. Suppose that I change the red-black insertion algorithm so that a newly inserted node x is colored black instead of red. Design your own rules to recolor / restructure the tree. To avoid the trivial answer of "continue by coloring x red and then proceed as usual", let's say I'd like to keep x black if possible, at least until a new insertion comes along. Do as much work as possible locally, i.e., in the neighborhood of x (look at color of parent, grandparent, uncle and sibling, if they exist). You are allowed to state that some steps continue as with the regular algorithm. 1 Note that x will be inserted as a leaf. To organize our cases, first assume WLOG that x is the left child of its parent p(x). Combinatorially (considering all options for the color of p(x) and the color/existence of its right child) this gives the six options below. x is not shown. A) p(x) B) p(x)∙ C) p(x)∙ For each case A−F : - If the case is not possible, explain why - If it is possible, do the following: - Draw the initial picture (with x inserted) - Describe the strategy - Draw the resulting picture One or more will require analysis of subcases. If there is a possible red-red conflict that needs to be addressed upwards as in the regular algorithm, just say so (no need for further explanation). Let g(x) denote the parent of p(x), if applicable.