Chromatic binary search trees: A structure for concurrent rebalancing

DOI10.1007/S002360050057MaRDI QIDQ1901709zbMATH OpenOpenAlexFDO

Authors Otto Nurmi, Eljas Soisalon-Soininen

Publication date 19 November 1995

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s002360050057

zbMATH Keywords

binary search treeschromatic treesconcurrencyrebalancingupdating

Mathematics Subject Classification ID

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

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.

Recommendations

• Efficient rebalancing of chromatic search trees
• Amortization results for chromatic search trees, with an application to priority queues
• Amortization results for chromatic search trees, with an application to priority queues
• scientific article; zbMATH DE number 1008516
• EFFICIENT REBALANCING OF B-TREES WITH RELAXED BALANCE

Cited in

(13)

• Amortization results for chromatic search trees, with an application to priority queues
• Relaxed multi-way trees with group updates.
• The amortized analysis of a non-blocking chromatic tree
• Red-black trees with constant update time
• Relaxed avl trees, main-memory databases and concurrency
• Skip trees, an alternative data structure to skip lists in a concurrent approach
• scientific article; zbMATH DE number 1760035 (Why is no real title available?)
• A fast contention-friendly binary search tree
• Efficient rebalancing of chromatic search trees
• Amortization results for chromatic search trees, with an application to priority queues
• The amortized analysis of a non-blocking chromatic tree
• Variants of (a,b)-trees with relaxed balance
• AVL trees with relaxed balance

This page was built for publication: Chromatic binary search trees: A structure for concurrent rebalancing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1901709)