Describe a red-black tree on \(n\) keys that realizes the largest possible ratio of red internal nodes to black internal nodes. What is this ratio? What tree has the smallest possible ratio, and what is the ratio?

In the event that \(n = 2^h - 1\) for some height \(h\) the answer from Exercise 13.1-6 applies and the largest possible ratio of red to black internal nodes is \(2:1\). Note however that this requires an even value for \(h\) in which case the bottom level of the tree is all red nodes. Odd values of \(h\) can only achieve a ratio of \(\sum\limits_{i=1}^{\lfloor h / 2 \rfloor} 2^{2i} : \sum\limits_{i=1}^{\lfloor h / 2 \rfloor} 2^{2i-1} + 1\) which is just slightly smaller than \(2 : 1\).

We cannot exceed this \(2 : 1\) ratio. We have maximized the number of red nodes by setting all even levels to red nodes so there is no alternative configuration that exceeds this ratio. The bottom-most level is all red nodes and so we cannot add another red node without violating red-black property 4. Similarly, we cannot remove any black node without violating both red-black properties 4 and 5.

Finally, if our red-black tree is not complete we can only achieve the highest possible ratio for \(n\) keys if our tree resmebles a heap, as in it is a complete tree except for the lowest depth (which need not be filled from the left as in a traditional heap). If our tree has this structure, we may apply a similar strategy as above and fill the largest level between either the lowest or second lowest level with red nodes and then work our way upwards applying alternating colors as we go. If our tree is structured differently, we may not be able to apply this strategy and our ratio will suffer. This means that given a proper structure \(n\)-key red-black tree can obtain a ratio which closely resembles the ratios outlined in the first paragraph of this solution, adjusted for the incomplete lowest level.