The remaining four chapters describe general techniques for designing functional data structures. We begin in this chapter with lazy rebuilding, a variant of global rebuilding [Ove83].

Batched Rebuilding

Many data structures obey balance invariants that guarantee efficient access. The canonical example is balanced binary search trees, which improve the worst-case running times of many tree operations from the O(n) required by unbalanced trees to O(log n). One approach to maintaining a balance invariant is to rebalance the structure after every update. For most balanced structures, there is a notion of perfect balance, which is a configuration that minimizes the cost of subsequent operations. However, since it is usually too expensive to restore perfect balance after every update, most implementations settle for approximations of perfect balance that are at most a constant factor slower. Examples of this approach include AVL trees [AVL62] and red-black trees [GS78].

However, provided no update disturbs the balance too drastically, an attractive alternative is to postpone rebalancing until after a sequence of updates, and then to rebalance the entire structure, restoring it to perfect balance. We call this approach batched rebuilding. Batched rebuilding yields good amortized time bounds provided that (1) the data structure is not rebuilt too often, and (2) individual updates do not excessively degrade the performance of later operations.