Parallel dictionaries using AVL trees
Abbreviated Journal Title
J. Parallel Distrib. Comput.
SEARCH-TREES; CONSTRUCTION; Computer Science, Theory & Methods
AVL (Adel'son-Vel'skii and Landis) trees are efficient data structures far implementing dictionaries. We present a parallel dictionary, using AVL trees, on the EREW PRAM by proposing optimal algorithms to perform k operations with p (1 less than or equal to p less than or equal to k) processors. An explicit processor scheduling is devised to avoid simultaneous reads in our parallel algorithm to perform k searches, which avoids the need for any additional memory in the parallelization. To perform multiple insertions and deletions, we identify rotations (in addition to AVL tree rotations) required to restore balance and present parallel algorithms to perform p insertions/deletions in O(log n + log p) time with p processors. (C) 1998 Academic Press.
Journal of Parallel and Distributed Computing
"Parallel dictionaries using AVL trees" (1998). Faculty Bibliography 1990s. 2357.