4 Red-Black Tree and (2,4)-Tree Deletion (20 pts) Preliminary Comments The lecture notes were based on Goodrich\&Tamassia's textbook, because they show the correspondence of RBTs to (2,4)-trees, which makes the former easier to understand as balanced trees. The CLRS version differs somewhat. You will need to read the CLRS text to answer this question. 1 The cases for insertion are similar between G\&T and CLRS, but the terminology differs (e.g., what the letters w,x,y, and z refer to). The cases for deletion differ: G\&T have 3 while CLRS have 4! Be careful because there are mirror images of every situation (e.g., is the double black no de a left child or a right child?): G\&T and CLRS may be describing the same situation with mirror image graphs. The top level metho ds in CLRS for RB-INSERT (p. 315) and RB-DELETE (p. 324) essentially do binary search tree (BST) insertion and deletion, and then call FIXUP methods to fix the red-black properties. Thus they are very similar to the BST methods Tree-Insert (p. 294) and Trea-Delete (p. 298). The real work specific to RBTs is in these fixup methods, so we will focus on them in these questions, but you should also study the top level metho ds to understand them as BST methods. Problems (a) RBT as (2,4)-Tree: Draw the (2,4)-tree that corresponds to the RBT shown below. (b) Deletion: Delete key 2 from the red/black tree shown above, and show the deletion in the (2,4) representation. Show every state of the RBT tree, including after the BST-style deletion and after each case applied by RB-Delete-Fixup. Clearly identify the colors of the nodes. Also show the state of the (2,4)-tree for each of these RBT states. If a double black node occurs (node x in CLRS), clearly identify which no de it is. For each state change, identify both G\&T case(s) from the web notes and the CLRS case(s) from the textbook that are applied in each of your steps. Your final diagram should show the RBT after RB-Delete-Fixup and the (2,4) tree representation that results. (c) More Deletion: Delete key 1 from the initial red/black tree shown above (NOT the tree that results from (b)), showing all steps as specified above