Suppose you want to perform an experiment to verify the problems that can be caused by random insert/remove pairs. Here is a strategy that is not perfectly random, but close enough. You build a tree with N elements by inserting N elements chosen at random from the range 1 to M = αN. You then perform N2 pairs of insertions followed by deletions. Assume the existence of a routine, randomInteger(a, b), which returns a uniform random integer between a and b inclusive.
a. Explain how to generate a random integer between 1 and M that is not already in the tree (so a random insertion can be performed). In terms of N and α, what is the running time of this operation?
b. Explain how to generate a random integer between 1 and M that is already in the tree (so a random deletion can be performed). What is the running time of this operation?
c. What is a good choice of α? Why?