2 Red-Black Trees (30 points) Consider the binary tree as shown in Figure 2. 65 50 80 10 60 85 5 45 62 Figure 2: Binary Tree: The letter next to each node (e.g., a, b) denotes the tree node, and the number inside each node is the key 2.1 Correctness (10 points) Is this binary tree a valid red-black tree? In other words, does it satisfy the red-black tree properties? If not, which node(s) violates the red-black tree properties, and why? You need to specify which properties are violated, if any. How would you modify the violating node(s) (e.g., color, key value) to make the binary tree a valid red-black tree? Hint: Your answer should incur the minimum amount of change on the current binary tree 2.2 Rotation (10 points) Let T denote the red-black tree in Figure 2 (or the corrected version if you need to modify the tree node(s) in the first question). How does the tree look like after the following operation: Right-Rotate(T, b). Is it still a valid red-black tree after this operation? Justify your answer 2.3 Insertion (10 points) Let T denote the red-black tree in Figure 2 (or the corrected version if you need to modify the tree node(s) in the first question). How does the tree look like after we insert a new node with key 90? Specify if you need to use Case 1, Case 2, or Case 3 in RB-INSERTION