Suppose you have a list of 50,000 names in a binary search tree, and you must frequently look for various names. It turns out that 20% of the names account for 75% of the lookups (finds). Instead of doing binary search tree find over all 50,000 names every time, consider the possibility of splitting the tree into two binary search trees, a high-frequency tree of 10,000 names, and a low-frequency tree of the remaining 40,000 names. To look up a name, you will first use binary search tree find on the high-frequency tree, and 75% of the time you will not need to go on to the second stage, where you use binary search tree find on the low-frequency tree. Is this scheme worth the effort? Justify your answer by calculating the number of nodes that are examined in the binary search tree find algorithm (on average for names in the tree), both in the new scheme and in the single tree of 50,000 names. For simplicity of calculation, you may assume that in each scheme the trees are perfectly balanced. (If this were a real system where lookups are common, then it would be worth the effort to arrange the tree so that it is as balanced as possible.) Also, for simplicity of calculation, you may assume that half of the nodes in the trees are at depth (logn)1, one-fourth are at depth (logn)2, etc. In the one-tree scheme, assume that the frequent and infrequent names are spread out evenly throughout the tree. (The reason for this assumption is that if the frequent names were near the bottom of the tree, then its performance would be worse.) In the two-tree scheme, assume that names are equally likely to be looked up within each tree. For the purposes of calculation/estimation, you can use the fact that i=1logn2i11 (which is similar to the summation we saw in hw \#1, but in that assignment you needed to calculate it exactly)