Abstract
We present parallel algorithms for constructing and maintaining balancedm-way search trees. These parallel algorithms have time complexity O(1) for ann processors configuration. The formal correctness of the algorithms is given in detail.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
D. E. Knuth, The Art of Computer Programming, Vol. 3, Sorting and Searching. Addison-Wesley, reading, Mass. (1973).
E. Horowitz and S. Sahni,Fundamentals of Data Structures, Computer Science Press, Potomac, Md. (1982).
P. K. Armstrong, U. S. Patent 4131947 (December 26, 1978).
M. J. Attallah and S. R. Kosaraju, A generalized dictionary machine for VLSI,IEEE Trans. on Comput. C-34(2):151–155 (February 1985).
J. L. Bentley and H. T. Kung, Two papers on tree-structured paralel computer, Dep. Comput. Sci. Carnegie Mellon University, Pittsburge, PA, Report CMU-CS-79-142 (1979).
M. J. Carey and C. D. Thompson, An efficient implementation of search trees on [logN+1] processors,IEEE Trans. on Comput. C-33(11):1038–1041.
C. E. Leiserson, Systolic priority queues, Dep. Comput. Sci. Carnegie Mellon University, Pittsburge, PA, Report CMU-CS-79-115 (1979).
T. A. Ottmann, A. L. Rosenberg, and L. J. Stockmeyer, A dictionary machine (for VLSI),IEEE Trans. on Comput. C-31:892–897 (September 1982).
A. K. Somani and V. K. Agarwal, An efficient VLSI dictionary machine,Proc. 11th Annu. ACM Intl. Symp. on Comput. Arch., pp. 142–150 (June 1984).
Y. Tanaka, Y. Nozaka, and A. Masuyama, Pipeline searching and sorting modules as components of data flow database computer,Proc. Int. Fed. Inform. Processing, pp. 427–432 (October 1980).
A. L. Fisher, Dictionary Machines with a small number of processors,Proc. 11th Annu. ACM Int. Symp. on Comput. Arch., pp. 151–156 (June 1984).
H. Chang and S. S. Iyengar, Efficient algorithms to globally balance a binary search tree,Com. ACM 27:695–702 (1984).
A. Moitra and S. S. Iyengar, A maximally parallel balancing algorithm for obtaining complete balanced binary trees,IEEE-T-SE, pp. 442–449 (1986).
Q. F. Stout and B. L. Warren, Tree rebalancing in optimal time and space, U. of Michigan Computing Research Laboratory, Ann Arbor, MI, CRL-TR-42-84.
U. Manber, Concurrent Maintenance of Binary Search Trees,IEEE Trans. on Soft. Engineering SE-10(6):777–784 (November 1984).
R. E. Tarjan and U. Vishkin, Finding biconnected components and computing tree functions in logarithmic parallel timeFOCS (1984).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Dekel, E., Peng, S. & Lyengar, S.S. Optimal parallel algorithms for constructing and maintaining a balancedm-way search tree. Int J Parallel Prog 15, 503–528 (1986). https://doi.org/10.1007/BF01407411
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01407411