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 $=\backslash$alpha N$.$ You then perform N$2$ 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 $\backslash$alpha $,$ 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 $\backslash$alpha $?$ Why?