Problem 6. Score: 16 In each of the following potential Red-Black (RB) trees, Bl
ID: 3718017 • Letter: P
Question
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.Explanation / Answer
A)
(1) (2) X (3) X (4) (5) X
Reason:
Properties of Red black tree:
1: Red - Black Tree must be a Binary Search Tree.
2: The ROOT node must colored BLACK.
3: The children of Red colored node must colored BLACK. (There should not be two consecutive RED nodes).
4: In all the paths of the tree there must be same number of BLACK colored nodes.
5: Every new node must inserted with RED color.
6: Every leaf (e.i. NULL node) must colored BLACK.
Red Black tree Example:
B)
1. Tree number:3
2. Reason it is not valid red black tree:
Property 3: The children of Red colored node must colored BLACK. (There should not be two consecutive RED nodes).
3. Can turn into valid Red Black Tree by(Cirlce one): Recoloring only
C)