Question 7 (9 marks)
Consider the following 2-3-4 tree and its corresponding red-black tree:
Based on the above answer the following questions:
What value(s) would be stored in the root node of the 2-3-4 tree after the insertion of the value 8? What value(s) would be stored in the node that now contains 8?
What value(s) would be stored in the root node of the 2-3-4 tree after the insertion of the value 42? What value(s) would be stored in the node that now contains 42?
What value(s) would be stored in the root node of the red-black tree after the insertion of the value 8? What would be the value in the parent node of the new node containing 8?
What value(s) would be stored in the root node of the red-black tree after the insertion of the value 42? What would be the value in the parent node of the new node containing 42?
How many different ways are there of representing a 2-node in a red-black tree?
How many different ways are there of representing a 3-node in a red-black tree?
How many different ways are there of representing a 4-node in a red-black tree?
Type the answer to this question into the file called q7.txt and submit it using the command:
$ submit q7
The above command will make a copy of q7.txt as your answer for this question.