Write out solutions to the exercises below, following the proof structures in the textbook. Please include the names of everyone in your group. $1.$ Describe a valid red$-$black tree on n keys that has the largest possible ratio of red internal nodes to black internal nodes. $($An internal node is a node that is not a leaf.$)$ Derive this ratio. Describe a tree that has the smallest possible ratio of red to black internal nodes, and give that ratio? $2.$ When we insert a new node into a red$-$black tree, we set the color of the newly inserted node n to red. Observe that if we had chosen to set n$\text{'}$s color to black, then property $4$ of a red$-$black tree would not be violated. Why didn't we choose to set n$\text{'}$s co XK$19$ lor to black? $3.$ Argue that in every n$-$node binary search tree, there are exactly n $1$ possible rotations. $4.$ If you take a subtree of a red$-$black tree, which of the five red$-$black properties are true for that subtree? How can we fix the other properties so we end up with a proper red$-$black tree from the subtree?