Worst case analysis of TreeMap data structure

Frédéric Fauberteau (1) , Serge Midonnet (1)

1 LIGM - Laboratoire d'Informatique Gaspard-Monge

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.

Domaines: Algorithme et structure de données [cs.DS]

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⟩