HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

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 :
Complete list of metadata

Cited literature [2 references]  Display  Hide  Download

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 2:06:48 PM
Last modification on : Friday, February 4, 2022 - 3:14:56 AM
Long-term archiving on: : Sunday, April 4, 2010 - 9:34:57 PM


  • HAL Id : inria-00073931, version 1



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



Record views


Files downloads