O(1) Time Algorithm on BSR for Constructinga Random Binary Search Tree

摘要：

Constructing a random binary search tree with n nodes needs θ(nlog n) time on RAM, and Ω(log n) time on n-processor EREW, CREW, or CRCW PRAM. In this paper, we propose an O(1) time algorithm on n-processor BSR PRAM for the problem, which is the first constant time solution to the problem on any model of computation.

关键词： random binary search tree BSR O(1) time algorithm

作者: Limin Xiang Kazuo Ushijiam Jianjun Zhao Tianqing Zhang Changjie Tang

作者单位: Department of Social Information Systems, Kyushu Sangyo University 2-3-1 Matsukadai, Higashi-ku, Fuk Department of Computer Science and Engineering, Fukuoka Institute of Technology 3-10-1 Wajiro-Higash Department of Computer Science, Sichuan University Chengdu 610064, Sichuan, China

会议类型: 国际会议

会议名称: Proceedings of The Fourth International Conference on Parallel and Distribyted Computing,Applications and Technologies(第四届并行与分布式计算应用与技术国际会议)

会议地点: 成都

会议语种:英文

页码: 599-602

在线出版日期: 2003-08-27（万方平台首次上网日期，不代表论文的发表时间）