An object of class IntSet represents a set of integers. There is a public constructor that takes no parameters and makes the set empty. Only two public methods are supported. s.member(n) returns true if n belongs to set s, and false otherwise. s.insert(n) produces a new set that contains all members of s as well as n. This data structure is persistent, and no methods are allowed to change a set. Write an implementation of the IntSet class, using an unordered linked list to represent a set. To insert, add the number to the beginning of the list, if it is not already in the list. You are allowed to use memory sharing.
Explain what it means to say that a given data structure performs each operation in amortized time O(1). Does that mean that every operation takes no more than c steps for some constant c?
What does it mean for the amortized time per operation to be O(log n)?
We looked an an implementation of first-in-first-out queues that uses two lists (one read forward, the other backwards) to represent the contents of a queue. Why didn't we take a simpler representation that uses a linked list with a pointer to the beginning and another pointer to the end? Would that have worked?
What tree do you get if, in the following binary search tree, you splay the 60 to the root? (Sorry for the crude graphics.)
180
/ \
140 250
/ \
55 150
/ \ \
24 72 155
/ \
60 100
/ \
58 65
If you start with an empty tree, how many steps does it take, in the worst case, to insert n things into a splay tree, one at a time?