Paper Info
Title
Parallel algorithms for red-black trees
Abstract
We present parallel algorithms for the following four operations on red–black trees: construction, search, insertion, and deletion. Our parallel algorithm for constructing a red–black tree from a sorted list of n items runs in O (1) time with n processors on the CRCW PRAM and runs in O ( log log n) time with n/ log log n processors on the EREW PRAM. Our construction algorithm does not require the assumptions that previous construction algorithms used. Each of our parallel algorithms for search, insertion, and deletion in red–black trees runs in O ( log n+ log k) time with k processors on the EREW PRAM, where k is the number of unsorted items to search for, insert, or delete and n is the number of nodes in a red–black tree. Keywords Red–black trees Balanced search trees Parallel algorithms Dictionary operations References [1] A.V. Aho J.E. Hopcroft J.D. Ullman The Design and Analysis of Computer Algorithms 1974 Addison-Wesley Reading, MA, USA [2] R. Bayer Data structure and maintenance algorithms Acta Inform. 1 1972 290 306 [3] R. Cole Parallel merge sort SIAM J. Comput. 17 1988 770 785 [4] S.A. Cook C. Dwork R. Reischuk Upper and lower time bounds for parallel random access machines without simultaneous writes SIAM J. Comput. 15 1986 87 97 [5] T.H. Cormen C.E. Leiserson R.L. Rivest Introduction to Algorithms 1990 MIT Press Cambridge, MA, USA [6] F.E. Fich P. Ragde A. Wigderson Relations between concurrent-write models of parallel computation SIAM J. Comput. 17 1988 606 627 [7] L.J. Guibas, R. Sedgewick, A dichromatic framework for balanced trees, Proc. FOCS’78, 1978, pp. 8–21. [8] J. JáJá An Introduction to Parallel Algorithms 1992 Addison-Wesley Reading, MA, USA [9] A. Moitra S.S. Iyengar A maximally parallel balancing algorithm for obtaining complete balanced binary trees IEEE Trans. Comput. 34 6 1985 563 565 [10] A. Moitra S.S. Iyengar Derivation of a parallel algorithm for balancing binary trees IEEE Trans. Software Eng. 12 3 1986 442 449 [11] W. Paul U. Vishkin H. Wagener Parallel dictionaries on 2–3 trees Proc. ICALP’83, Lecture Notes in Comput. Sci. vol. 154 1983 Springer Berlin 597 609 [12] R. Sedgewick Algorithms in C++ 1992 Addison-Wesley Reading, MA, USA [13] R.E. Tarjan Updating a balanced search tree in O(1) rotations Inf. Process. Lett. 16 1983 253 257 [14] R.E. Tarjan Data Structures and Network Algorithms 1983 SIAM Philadelphia, PA, USA [15] B.F. Wang G.H. Chen Cost-optimal parallel algorithms for constructing 2-3 trees J. Parallel Distributed Comput. 11 1991 257 261
Year
DOI
Venue
2001
10.1016/S0304-3975(00)00287-5
Theor. Comput. Sci.
Keywords
DocType
Volume
parallel algorithm,red-black tree
Journal
262
Issue
ISSN
Citations 
1-2
Theoretical Computer Science
10
PageRank 
References 
Authors
0.63
9
2
Name
Order
Citations
PageRank
Heejin Park123521.63
Kunsoo Park21396171.00