Chromatic binary search trees: A structure for concurrent rebalancing. (English) Zbl 0849.68026

Nurmi, Otto; Soisalon-Soininen, Eljas

Acta Inf. 33, No. 6, 547-557 (1996).

We propose a new rebalancing method for binary search trees that allows rebalancing and updating to be uncoupled. In this way we obtain fast updates and, whenever the search tree is accessed by multiple users, a high degree of concurrency. The trees we use are obtained by relaxing the balance conditions of red-black trees. The relaxed red-black trees, called chromatic trees, contain information of possible imbalance such that the rebalancing can be done gradually as a shadow process, or it can be performed separately when no urgent operations are present.

Reviewer: O.Nurmi (Helsinki)

MSC:

68P10	Searching and sorting
68P05	Data structures
68Q10	Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68P15	Database theory

Keywords:

binary search trees; rebalancing; updating; concurrency; chromatic trees