1. Provide algorithms that are sensitive to the relative sizes of n and m.

(a) Let R1 be a red-black tree with n elements. Let R2 be a red-black tree with m elements, where m ? n. How fast can you construct a red-black tree containing all elements from R1 and R2? (Hint: Take advantage of the structure that you have. What should you do if one tree has just a few elements? What if they both have the same number of elements?)

(b) Same as (a), but suppose that you are given input such that all the values in R1 are smaller than all the values in R2. (Hint: Start with an easy case: what if the black height of both trees is the same? Pick a target time complexity, and then think about all things that you are allowed to do within that time, and how they might help.)