Relaxed Balancing in Search Trees

Eljas Soisalon-Soininen () and Peter Widmayer ()
Additional contact information
Eljas Soisalon-Soininen: Helsinki University of Technology, Laboratory of Information Processing Science
Peter Widmayer: ETH Zentrum, Institut für Theoretische Informatik

A chapter in Advances in Algorithms, Languages, and Complexity, 1997, pp 267-283 from Springer

Abstract: Abstract 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.

Keywords: Search Tree; Child Node; Parent Node; Concurrency Control; Search Path (search for similar items in EconPapers)
Date: 1997
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4613-3394-4_13

Ordering information: This item can be ordered from
http://www.springer.com/9781461333944

DOI: 10.1007/978-1-4613-3394-4_13

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().