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

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)


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