Red-black trees with constant update time

DOI10.1007/s00236-019-00335-9zbMath1423.68124arXiv1804.02112OpenAlexW2964158898WikidataQ127843088 ScholiaQ127843088MaRDI QIDQ2422774

Amr Elmasry, Mostafa Kahla, Fady Ahdy, Mahmoud Hashem

Publication date: 20 June 2019

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1804.02112

Mathematics Subject Classification ID

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

Related Items

Regular numeral systems for data structures

Cites Work

• Unnamed Item
• Unnamed Item
• The design of dynamic data structures
• A balanced search tree O(1) worst-case update time
• Amortized constant relaxed rebalancing using standard rotations
• A new data structure for representing sorted lists
• Efficient rebalancing of chromatic search trees
• Updating a balanced search tree in 0(1) rotations
• Chromatic binary search trees: A structure for concurrent rebalancing
• Organization and maintenance of large ordered indexes
• Symmetric binary B-trees: Data structure and maintenance algorithms
• A SIMPLE BALANCED SEARCH TREE WITH O(1) WORST-CASE UPDATE TIME
• Red-black trees in a functional setting
• Balanced search trees made simple
• Binary Search Trees of Bounded Balance
• relaxed balance for search trees with local rebalancing