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. 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 work has been partly supported by the French CNRS Coordinated Research Program on Parallelism, Networks and Systems PRS, the EU HCM Program under Contract ERBCHGECT 920009 and the EU Esprit BRA Program ALCOM 117141 and DGICYT under grant PB95-0787 (project KOALA).
Chapter PDF
Keywords
References
G. M. Adel'son Vel'skî and E. M. Landis. An algorithm for the organization of the information. Soviet Mathematics Doklady, (3):1259–1263, 1962.
L. Boug, J. Gabarró, and X. Messeguer. Concurrent AVL revisited: self-balancing distributed search. Research Report RR95-45, LIP, ENS Lyon, France, 1995. Available at URL http://www.ens-lyon.fr/LIP
L. Boug, J. Gabarró, X. Messeguer, and N. Schabanel. Concurrent rebalancing of AVL trees: A fine-grained approach. Research Report RR97-13, LIP, ENS Lyon, France, 1997. Available at URL http://www.ens-lyon.fr/LIP
R. Bayer and M. Schkolnicc. Concurrency of operations on B-trees. Acta Informatica, 9(1):1–21, 1977.
E. W. Dijkstra, L. Lamport, A. J. Martin, C. S. Scholten, and E. F. M. Steffens. On the fly garbage collection: an exercice in cooperation. Comm. ACM, 21(11):966–975, 1978.
C. S. Ellis. Concurrent search and insertion in AVL trees. IEEE Trans. Comp., C-29(9):811–817, 1980.
N. Francez. Distributed termination. ACM Trans. Progr. Languages and Systems, 2:42–55, 1980.
J. L. S. Kessels. On the fly optimisation of data structures. Comm. ACM, 26(11):895–901, 1983.
H. T. Kung and P. L. Lehman. Concurrent manipulation of binary serch trees. ACM Trans. Database Systems, 5(3):354–382, 1980.
D. E. Knuth. The art of computer programming, Fundamental algorithms. Addison Wesley, 1973.
K. S. Larsen. AVL trees with relaxed balance. In Proc. Int. Parallel Processing Symp., pages 888–893. IEEE Comp. soc., 1994.
O. Nurmi and E. Soisalon-Soininen. Chromatic binary serach trees. Acta Informatica, 33(6):547–557, 1996.
O. Nurmi, E. Soisalon-Soininen, and D. Wood. Concurrency control in database structures with relaxed balance. ACM Symp. Princ. Distributed Systems, pages 170–176, 1987.
O. Nurmi, E. Soisalon-Soininen, and D. Wood. Concurrent balancing and updationg of AVL trees. Technical Report 1992 ITKO-1376, Helsinki Univ. of Techn., Dept. Comp. Sciences, 1992. *** DIRECT SUPPORT *** A0008C42 00015
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bougés, L., Gabarró, J., Messeguer, X., Schabanel, N. (1997). Concurrent rebalancing of AVL trees: A fine-grained approach. In: Lengauer, C., Griebl, M., Gorlatch, S. (eds) Euro-Par'97 Parallel Processing. Euro-Par 1997. Lecture Notes in Computer Science, vol 1300. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0002766
Download citation
DOI: https://doi.org/10.1007/BFb0002766
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63440-9
Online ISBN: 978-3-540-69549-3
eBook Packages: Springer Book Archive