4.14 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 alreadyin 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? | |
| View Solution | |
| << Back | Next >> |