Optimal parallel algorithms for constructing and maintaining a balanced m-way search tree

DOI10.1007/BF01407411MaRDI QIDQ1099627zbMATH OpenOpenAlexFDO

Authors Eliezer Dekel, Shietung Peng, S. Sitharma Iyenga

Publication date 1986

Published in International Journal of Parallel Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01407411

zbMATH Keywords

MIMDparallel algorithmssearch trees

Mathematics Subject Classification ID

Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25)

Review text

We present parallel algorithms for constructing and maintaining balanced m-way search trees. These parallel algorithms have time complexity O(1) for an n processors configuration. The formal correctness of the algorithms is given in detail.

Recommendations

• scientific article; zbMATH DE number 2087827
• A Maximally Parallel Balancing Algorithm for Obtaining Complete Balanced Binary Trees
• A unified approach to the parallel construction of search trees
• scientific article; zbMATH DE number 4155887
• Parallel Algorithms with Optimal Speedup for Bounded Treewidth
• Parallel algorithms with optimal speedup for bounded treewidth
• Parallel construction of binary trees with near optimal weighted path length
• Derivation of a parallel algorithm for balancing binary trees
• Cost-optimal parallel algorithms for constructing B-trees
• On a sublinear time parallel construction of optimal binary search trees

Cites work

• A Generalized Dictionary Machine for VLSI
• Derivation of a parallel algorithm for balancing binary trees
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3628373 (Why is no real title available?)
• scientific article; zbMATH DE number 3635458 (Why is no real title available?)

Cited in

(7)

• A unified approach to parallel depth-first traversals of general trees
• An optimal parallel algorithm for merging using multiselection
• Cost-optimal parallel algorithms for constructing B-trees
• A unified approach to the parallel construction of search trees
• A Maximally Parallel Balancing Algorithm for Obtaining Complete Balanced Binary Trees
• Derivation of a parallel algorithm for balancing binary trees
• Parallel algorithms for red--black trees

This page was built for publication: Optimal parallel algorithms for constructing and maintaining a balanced m-way search tree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1099627)