UC BERKELEY
EECS technical reports
TECHNICAL REPORTS


CSD-82-101.pdf
Oskicat catalog record
Conditions of Use

Archive Home Page

An Efficient Implementation of Search Trees on O(lg N) Processors

Authors:
Carey, Michael J.
Thompson, Clark D.
Technical Report Identifier: CSD-82-101
April 21, 1982
CSD-82-101.pdf

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.