An Efficient Implementation of Search Trees on O(lg N) Processors
Carey, Michael J.
Thompson, Clark D.
Technical Report Identifier: CSD-82-101
April 21, 1982
Abstract: A scheme for maintaining a balanced search tree on O(lg N) parallel processors is described. O(lg N) search, insert, and delete operations are allowed to run concurrently, with each operation executing in O(lg N) timesteps. The scheme is based on pipelined versions of top-down 2-3-4 tree manipulation algorithms.