Parallel dictionaries using AVL trees

    Authors

    M. Medidi;N. Deo

    Comments

    Authors: contact us about adding a copy of your work at STARS@ucf.edu

    Abbreviated Journal Title

    J. Parallel Distrib. Comput.

    Keywords

    SEARCH-TREES; CONSTRUCTION; Computer Science, Theory & Methods

    Abstract

    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 Title

    Journal of Parallel and Distributed Computing

    Volume

    49

    Issue/Number

    1

    Publication Date

    1-1-1998

    Document Type

    Article

    Language

    English

    First Page

    146

    Last Page

    155

    WOS Identifier

    WOS:000073870000010

    ISSN

    0743-7315

    Share

    COinS