Title

Parallel Dictionaries Using AVL Trees

Abstract

AVL (Adel'son-Vel'skii and Landis) trees are efficient data structures for implementing dictionaries. We present a parallel dictionary, using AVL trees, on the EREW PRAM by proposing optimal algorithms to performkoperations withp(1 ≤p≤k) processors. An explicit processor scheduling is devised to avoid simultaneous reads in our parallel algorithm to performksearches, 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 performpinsertions/deletions inO(logn+ logp) time withpprocessors. © 1998 Academic Press.

Publication Date

2-25-1998

Publication Title

Journal of Parallel and Distributed Computing

Volume

49

Issue

1

Number of Pages

146-155

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1006/jpdc.1998.1432

Socpus ID

0012882890 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/0012882890

This document is currently not available here.

Share

COinS