Skip to Main content Skip to Navigation
Reports

Concurrent AVL Revisited: Self-Balancing Distributed Search Trees

Luc Bougé 1 Joachim Gabarrò 2 Xavier Messeguer 2
1 REMAP - Regularity and massive parallel computing
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : We address the concurrent insertion and deletion of keys in binary almost balanced search trees (AVL trees). We show that this problem can be studied through the self-reorganization of distributed systems of processes controlled by local evolution rules in the line of the approach of Dijkstra and Scholten. This yields a simple and abstract presentation of the insertion and deletion mechanisms. In particular, we show that our approach encapsulates a number of previous attempts described in the literature. They can in fact be seen as ad hoc specializations of the nondeterministic evolution rules. 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 trees?
Document type :
Reports
Complete list of metadata

Cited literature [2 references]  Display  Hide  Download

https://hal.inria.fr/inria-00073931
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 2:06:48 PM
Last modification on : Monday, November 16, 2020 - 3:56:03 PM
Long-term archiving on: : Sunday, April 4, 2010 - 9:34:57 PM

Identifiers

  • HAL Id : inria-00073931, version 1

Collections

Citation

Luc Bougé, Joachim Gabarrò, Xavier Messeguer. Concurrent AVL Revisited: Self-Balancing Distributed Search Trees. [Research Report] RR-2761, INRIA. 1995. ⟨inria-00073931⟩

Share

Metrics

Record views

239

Files downloads

589