Parallel dictionaries using AVL trees

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.