O(1) time algorithm on BSR for constructing a random binary search tree
Limin Xiang, Kazuo Ushijiam, Jianjun Zhao, Tianqing Zhang, Changjie Tang · 2004
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.