Abstract :
We present a unified parallel algorithm for constructing various search trees. The tree construction is based on a unified scheme, called bottom-level balancing, which constructs a height balanced search tree having a uniform distribution of keys. The algorithm takes O(loglogN) time using N/loglogN processors on the EREW PRAM model, and 0(1) time with N processors on the CREW PRAM model, where N is the number of keys in the tree.
