Chromatic binary search trees: A structure for concurrent rebalancing
type: Item
instance of: scholarly article
title: Chromatic binary search trees: A structure for concurrent rebalancing
zbMATH Open document ID: 0849.68026
author: Otto Nurmi
author: Eljas Soisalon-Soininen
published in: Acta Informatica
publication date: 1995-11-19T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 68P05
Mathematics Subject Classification ID: 68Q10
Mathematics Subject Classification ID: 68P15
zbMATH DE Number: 814159
zbMATH Keywords: binary search trees
zbMATH Keywords: rebalancing
zbMATH Keywords: updating
zbMATH Keywords: concurrency
zbMATH Keywords: chromatic trees
MaRDI profile type: Publication
full work available at URL: s002360050057
OpenAlex ID: W4241183800
DOI: 10.1007/S002360050057
description: scientific article; zbMATH DE number 814159