CS557A: Algorithms Fall 2020

Assignment 4 Answer the questions below. You may submit scanned or photo’d copies of handwritten submissions, but use the PDF format. You may also submit your answers using Microsoft Word or other electronic word processors, but convert to PDF format before submission.

1. Consider the red-black tree above. For each of the value below, indicate where in the tree they would be inserted. Give you answer as: :Left or :Right, where is the color of the node to be added, is the value in the node under which the value is added, and Left/Right is used to indicate whether the value is added as a left or right child, respectively. a. 50 b. 192 c. 119

2. Will any of the additions above require a color switch or a rebalance of the red-black tree? Why or why not? 3. For each of the scenarios below of a partial red-black, indicate whethere a color switch or a rebalance is required

and then perform the action. Indicate whether it is possible that a further change is required higher in the tree. a.