Clark D. Thompson and Michael J. Carey

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-82-101

, 1982

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1982/CSD-82-101.pdf

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.

---

BibTeX citation:

@techreport{Thompson:CSD-82-101,
    Author= {Thompson, Clark D. and Carey, Michael J.},
    Title= {An Efficient Implementation of Search Trees on O(lg N) Processors},
    Year= {1982},
    Month= {Apr},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1982/6204.html},
    Number= {UCB/CSD-82-101},
    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.},
}

EndNote citation:

%0 Report
%A Thompson, Clark D. 
%A Carey, Michael J. 
%T An Efficient Implementation of Search Trees on O(lg N) Processors
%I EECS Department, University of California, Berkeley
%D 1982
%@ UCB/CSD-82-101
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1982/6204.html
%F Thompson:CSD-82-101