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 metadatas

Cited literature [12 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00628464
Contributor : Serge Midonnet <>
Submitted on : Tuesday, March 19, 2013 - 1:00:24 PM
Last modification on : Wednesday, February 26, 2020 - 7:06:06 PM
Long-term archiving on: : Thursday, June 20, 2013 - 4:21:25 PM

File

jrwrtc2008.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00628464, version 1

Citation

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⟩

Share

Metrics

Record views

363

Files downloads

723