Problem 6. Score: 16 In each of the following potential Red-Black (RB) trees, Black nodes are shown as shaded and Red nodes are shown as unshaded. NIL nodes are not shown but are still present in the tree. (1) (2) (3) (4) (5) OO 3 O OO O d a) (10 pts) Consider a potential RB tree valid if it does not violate any properties of RB trees, and not valid if it does violate a property of RB trees. Write an 'X' next to the number of all potential RB tree(s) above that are not valid. (1) _ (2) _ (3) _ (4)_ (5) _ b) (3 pts) For one of the tree(s) you indicated, identify the tree and state why it is not a valid RB tree and how it can be transformed into a valid one. ?. Tree number: ii. (1 pt) Reason it is not a valid RB tree: iii. (2 pts) Can be turned into a valid RB tree by (circle one): 2 rotations plus recoloring recoloring only 1 rotation plus recoloring c) (3 pts) Suppose the integers 1, 2, 3, 4, 5, 6, 7 are stored in potential RB tree (5) above. Write the values 1 thru 7 inside the nodes of tree (5) where they must appear for the tree to be a binary search tree