Question :
Suppose that you have a balanced binary search tree that does not support delete.
(It does support the other dictionary operations, e.g., search, insert, and in-order traversal of the elements in the structure.)
Consider the following amortized way to support deletes.
Whenever you need to delete an element, you search for it and set a flag to indicate that it has been deleted.
(Thus, the element stays in the data structure, we know to ignore it.)
Whenever half of the elements in the structure have been marked as deleted, we do an in-order traversal to get all (nondeleted) elements in the structure, and then rebuild.
What is the amortized cost to delete elements?