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?
Type de document :
[Research Report] RR-2761, INRIA. 1995
Liste complète des métadonnées

Littérature citée [2 références]  Voir  Masquer  Télécharger
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 14:06:48
Dernière modification le : vendredi 20 avril 2018 - 15:44:24
Document(s) archivé(s) le : dimanche 4 avril 2010 - 21:34:57



  • 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〉



Consultations de la notice


Téléchargements de fichiers