Height-relaxed AVL rebalancing: A unified, fine-grained approach to concurrent dictionaries.

Abstract : We address the concurrent rebalancing of almost balanced binary search trees (AVL trees). Such a rebalancing may for instance be necessary after successive insertions and deletions of keys. We show that this problem can be studied through the self-reorganization of distributed systems of nodes controlled by local evolution rules in the line of the approach of Dijkstra and Scholten. This yields a much simpler algorithm that the ones previously known. Based on the basic rebalancing framework, we describe algorithms to manage concurrent insertion and deletion of keys. Finally, this approach is used to emulate other well known concurrent AVL algorithms. As a by-product, this solves in a very general setting an old question raised by H.T. Kung and P.L. Lehman: where should rotations take place to rebalance arbitrary search trees? This paper is the extended version of the previous research report RR1997-13
Document type :
Reports
Complete list of metadatas

Cited literature [25 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02101955
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:10:41 AM
Last modification on : Wednesday, November 20, 2019 - 2:50:31 AM

File

RR1998-18.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101955, version 1

Collections

Citation

Luc Bougé, Joaquim Gabarro, Xavier Messeguer, Nicolas Schabanel. Height-relaxed AVL rebalancing: A unified, fine-grained approach to concurrent dictionaries.. [Research Report] LIP RR-1998-18, Laboratoire de l'informatique du parallélisme. 1998, 2+34p. ⟨hal-02101955⟩

Share

Metrics

Record views

8

Files downloads

23