(There are 10 extra points to be had) 1. [10] C-9.7 (Old edition: C-7.9) 2. [10] C-9.11 (Old edition: C-7.12) 3. [10] C-9.12 (Old edition: no equivalent --Let T and U be (2,4) trees storing n and m terms respectively, such that all the items in T have keys less than the keys of all the items in U. Describe an O(logn+logm) time method for joining T and U into a single tree that stores all the items in T and U (destroying the old versions ofT and U).) 4. [10] C-9.17 (Old edition: no equivalent --
Show that the nodes of any AVL tree T can be colored "red" and "black" so that T becomes a red=black tree. )
5. [5] R-9.10 (Old edition: no equivalent --An alternative way of performing a split at a node v in a (2,4) tree is to partition v into v" and v"", with v" being a 2-node and v"" being a 3-node. Which of the keys k1,k2,k3,k4 do we store at v's parent in this case? Why? )
In the following, use counterexamples with at least 5 keys. 6. [5] R-9.3 (Old edition: R-7.3) 7. [5] R-9.4 (Old edition: R-7.4) 8. [5] R-9.11 (Old edition: no equivalent --Professor Amongus claims that a (2,4) tree storing a set of items will always have the same structure, regardless of the order in which the items are inserted. Show that Professor Amongus is wrong. )