Amortization results for chromatic search trees, with an application to priority queues

DOI10.1006/JCSS.1997.1511zbMATH Open0897.68034OpenAlexW2055947636MaRDI QIDQ1384535FDOQ1384535

Authors: Rolf Fagerberg, Kim S. Larsen, Joan Boyar 

Publication date: 4 August 1998

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.1997.1511

Recommendations

• Amortization results for chromatic search trees, with an application to priority queues
• Chromatic binary search trees: A structure for concurrent rebalancing
• Efficient rebalancing of chromatic search trees
• relaxed balance for search trees with local rebalancing

zbMATH Keywords

shared-memory asynchronous parallel architectures

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10)

Cites Work

• Scheduling multithreaded computations by work stealing
• Symmetric binary B-trees: Data structure and maintenance algorithms
• On-the-fly optimization of data structures
• Organization and maintenance of large ordered indexes
• Concurrent manipulation of binary search trees
• Efficient locking for concurrent operations on B-trees
• A new data structure for representing sorted lists
• B-trees in a system with multiple users
• A New Method for Concurrency in B-Trees
• Concurrent operations on \(B^ *\)-trees with overtaking
• Title not available (Why is that?)
• Concurrent access of priority queues
• Efficient rebalancing of chromatic search trees
• Amortization results for chromatic search trees, with an application to priority queues
• Chromatic binary search trees: A structure for concurrent rebalancing
• Relaxed avl trees, main-memory databases and concurrency
• EFFICIENT REBALANCING OF B-TREES WITH RELAXED BALANCE
• AVL trees with relaxed balance

Cited In (10)

• Amortization results for chromatic search trees, with an application to priority queues
• Relaxed balance through standard rotations
• Efficient rebalancing of chromatic search trees
• Title not available (Why is that?)
• Amortization results for chromatic search trees, with an application to priority queues
• Relaxed multi-way trees with group updates.
• Chromatic binary search trees: A structure for concurrent rebalancing
• Variants of \((a,b)\)-trees with relaxed balance
• AVL trees with relaxed balance
• The amortized analysis of a non-blocking chromatic tree

Uses Software

• heapsort

This page was built for publication: Amortization results for chromatic search trees, with an application to priority queues

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