Note: For any question asking you to draw a tree, a text description is acceptable if it allows us to reconstruct 1. (5 points) Draw the 2-3-4 search tree that results from inserting 5,1,19,25,17,21,20,9, 15, 14 (in that 2. (5 points) Draw the Red-Black BST that results from inserting 5, 1,19,25,17,21,20,9,15,14 (in that the tree without needing to understand the tree rules order) into an initially empty tree. order) into an initially empty tree. Distinguish red from black edgesodes in some reasonable way (different colored pencil, dotted lines, ...) 3. (5 points) Draw the Red-Black BST that results from inserting 1,2,3,4,5,6,7,8,9,10,11 (in that order) into an initially empty tree (3 points) In the worst case, how many probes are required to insert N keys into an initially empty hash table using linear probing? Explain how this can happen. 5. Assume we have an initially empty hash table which uses linear probing and the hash function h(k) = 11k mod M Further, assume that we insert items with keys 4, 0, 18, 24, 16, 20, 19, 8, 14, 13 in that order. Give the contents of the hash table for each of the following table sizes (a) (3 points) M 16 (b) (3 points) M-10 6. Say you are given a hash table size of M = 1123 and we insert keys into the table where collisions are resolved with linear probing. Assume we are using a good hash function that effectivelv hashes to a random cell =, ave probes/hit =- 1 + ave probes/miss =-(1 + (a) (2 points) What is the highest number of keys N I can put in the table if I want the average number of probes on a miss to be 18? (b) (2 points) How about 8