Skip to Main content Skip to Navigation
Conference papers

Worst case analysis of TreeMap data structure

Abstract : Data structures with relaxed balance eases the update of shared resources on asynchronous parallel architectures. This improvement is obtained by a better locking scheme of the data structure. In this paper, we describe the complexity and analyze the worst case cost of access operations on such a structure. We propose a data structure with the same properties as Java TreeMap but implemented with chromatic search tree; a tree with relaxed balance. The aim of our structure is to provide a more efficient TreeMap we can use in concurrent and real-time applications.
Document type :
Conference papers
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download
Contributor : Serge Midonnet Connect in order to contact the contributor
Submitted on : Tuesday, March 19, 2013 - 1:00:24 PM
Last modification on : Saturday, January 15, 2022 - 3:58:16 AM
Long-term archiving on: : Thursday, June 20, 2013 - 4:21:25 PM


Files produced by the author(s)


  • HAL Id : hal-00628464, version 1


Frédéric Fauberteau, Serge Midonnet. Worst case analysis of TreeMap data structure. 2nd Junior Researcher Workshop on Real-Time Computing (JRWRTC'08), Oct 2008, Rennes, France. pp.33-36. ⟨hal-00628464⟩



Record views


Files downloads