The drawing to the right epresents a valid red$-$black tree, aug$-$

mented with subtree sizes. Show how to insert the new node $17.$

You must show both the initial insertion, and any changes made

by RB$-$repair. You must also show the updates to any attributes

of the tree nodes. Explain briefly why the black height of the

tree does not change after this insert. After $17$ is inserted, is

there another node that could be inserted which would cause

the black$-$heigh to increase?

$($b$)10$ points For each of the following statements, decide if the statement is true for false, and briefly

$($one sentence!$)$ justify your answer.

A red$-$black tree has black height $4.$ What is the maximum number of nodes possible in the tree?

A red$-$black tree has $45$ nodes. What is the smallest possible black height for such a tree?

A red$-$black tree has $45$ nodes. What is the largest possible tree height?

A red$-$black tree has $45$ nodes. Is it possible that all nodes in the tree are colored black?

A red$-$black tree has $7$ nodes and height $2.$ Is there only one possible coloring for such a tree?

$($c$)4$ points

Suppose that there are n nodes in a RBT$.$ What is the maximum black$-$height of the tree? $($express

your answer in terms of n $).$ What is the maximum height of tree? $($express your answer in terms of n $)?$

Use this result to determine if it is possible to have a red$-$black tree on $100$ nodes of height $15.$ If so$,$ draw

the tree, if not, explain why not.

$($d$)3$ points. Draw an example of a RBT on $16$ nodes with black height $3$ that has two different

possible colorings. Show the different possible colorings.

$($e$)4$ points Explain why it takes O$($n log n$)$ time to build a RBT$.$ Next, suppose we have already built

a BST$.$ Explain how to convert the BST to a RBT in O$($n$)$ time. How you do the conversion is up to you

$($you don't have to maintain the original shape in any way$).$ solve step by step clearly