Relaxed Balancing in Search Trees

We consider search trees within the scheme that rebalancing transformations need not be connected with updates but may be delayed. Moreover, the various rebalancing operations are made to be composed of small local steps. This scheme of maintenance of search trees is called relaxed balancing in contrast to standard strict balancing (each update includes the required operations for keeping the tree in balance). With relaxed balancing we can solve the concurrency control problem of search trees efficiently: the maintenance of search trees is divided into operations each of which needs to lock only a small constant number of nodes at a time. Relaxed balancing is important for efficiency even in sequential applications where updates occur in bursts. In this paper, we consider, in particular, the AVL type balancing operations—tree rotations—in implementing relaxed balancing. Our main contribution is that our scheme fulfills the following desirable global properties of search trees, despite the local nature of operations: no rebalancing operation can yield a less balanced tree (in the sense of the AVL balance condition), and each applied tree rotation really corresponds to a real imbalance situation in the tree. This implies, for example, that if the underlying search tree happens to fulfill the AVL tree balance condition before any rebalancing has been done, then the separate rebalancing processes will not perform any rotation in the tree.