A Unified Approach to the Parallel Construction of Search Trees |
| |
| Affiliation: | 1. Department of Mathematics & Statistics, The University of Winnipeg, Canada;2. Department of Mathematics & Statistics, University of Victoria, Canada |
| |
| 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 perfectly balanced search tree having a uniform distribution of keys. The algorithm takes O(log log N) time using N/log log N processors on the EREW PRAM model, and O(1) time with N processors on the CREW PRAM model, where N is the number of keys in the tree. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
