O(1) time algorithm on BSR for constructing a random binary search tree
説明
Constructing a random binary search tree with n nodes needs /spl theta/(nlog n) time on RAM, and /spl omega/(log n) time on n-processor EREW, CREW, or CRCW PRAM. 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.
収録刊行物
-
- Proceedings of the 8th International Scientific and Practical Conference of Students, Post-graduates and Young Scientists. Modern Technique and Technologies. MTT'2002 (Cat. No.02EX550)
-
Proceedings of the 8th International Scientific and Practical Conference of Students, Post-graduates and Young Scientists. Modern Technique and Technologies. MTT'2002 (Cat. No.02EX550) 599-602, 2004-03-02
IEEE