Lazy Rebuilding

Prev: Eliminating Amortization Next: Numerical Representations

Prev: Eliminating Amortization Next: Numerical Representations

8.1 Batched Rebuilding

Exercises

Exercise 8.1

Extend the red-black trees of Section 3.3 with a delete function using these ideas. Add a boolean field to the T constructor and maintain estimates of the numbers of valid and invalid elements in the tree.

Assume for the purposes of these estimates that every insertion adds a new valid element and that every deletion invalidates a previously valid element. Correct the estimates during rebuilding. You will find Exercise 3.9 helpful in rebuilding the tree.

8.2 Global Rebuilding

Exercises

Exercise 8.2

Prove that calling exec twice at the beginning of each rotation, and once for every remaining insertion or deletion, is enough to finish the rotation on time. Modify the code accordingly.

Exercise 8.3

Replace the lenf and lenr fields with a single diff field that maintains the difference between the lengths of f and r. diff may be inaccurate during rebuilding, but must be accurate by the time rebuilding is finished.

8.4 Double-Ended Queues

Exercises

Exercise 8.4

We cannot extend Hood and Melville’s real-time queues with a cons function quite so easily, because there is no easy way to insert the new element into the rotation state. Write a functor that extends any implementation of queues with a constant-time cons function, using the type:

type a Queue = a list * a Q.Queue

cons should insert elements into the new list, and head and tail should remove elements from the new list whenever it is non-empty.

Exercise 8.5

Prove Theorem 8.1.

Exercise 8.6

Explore the tradeoffs in the choice of the balance constant c.

1. Construct a sequence of operations for which the choice c = 4 would be significantly faster than c = 2.
2. Construct a sequence of operations for which c = 2 would be significantly faster than c = 4.

Exercise 8.7

Show that executing one suspension per stream per insertion and two suspensions per stream per deletion is enough to guarantee that both schedules are completely evaluated before the next rotation.

8.5 Chapter Notes