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

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

128

Files downloads

385