×

Parallel computation on 2-3-trees. (English) Zbl 0531.68017

Summary: Our model of computation is a parallel computer with k synchronized processors \(P_ 1,...,P_ k\) sharing a common random access storage, where simultaneous access to the same storage location by two or more processors is not allowed. Suppose a 2-3 tree T with n leaves is implemented in the storage, suppose \(a_ 1,...,a_ k\) are data that may or may not be stored in the leaves, suppose \(a_ 1\leq...\leq a_ k\) and for all i processor \(P_ i\) knows \(a_ i\). We show how to search for \(a_ 1,...,a_ k\) in the tree T, how to insert these data into the tree and how to delete them from the tree in 0 (log n\(+\log k)\) steps.

MSC:

68P10 Searching and sorting
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68N25 Theory of operating systems
PDF BibTeX XML Cite
Full Text: EuDML

References:

[1] 1. A. AHO, J. HOPCROT and J. D. ULLMAN, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, Massachusetts, 1976. Zbl0326.68005 · Zbl 0326.68005
[2] 2. R. BAYER and M. SCHKOLNICK, Concurrency of Operations on B-Trees, Acta Informatica, Vol. 9, 1977, pp. 1-21. Zbl0343.68022 MR455599 · Zbl 0343.68022
[3] 3. Ellis C. SCHLATTER, Concurrent Search and Insertion in 2-3-Trees, Acta Informatica, Vol. 14, 1980, pp. 63-86. Zbl0413.68065 MR581380 · Zbl 0413.68065
[4] 4. H. WAGENER, Parallele Bearbeitung von 2-3-Bäumen, Diplomarbeit, Fakultät für Mathematik, Universität Bielefeld, 1982.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.