Reconstructing a Binary Tree from Its Traversals in Doubly Logarithmic CREW Time
| Autor: | Zhaofang Wen, Stephan Olariu, Michael Overstreet |
|---|---|
| Rok vydání: | 1995 |
| Předmět: |
TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES
Binary tree Logarithm Computer Networks and Communications Parallel algorithm Preorder Eulerian path Binary logarithm Theoretical Computer Science Combinatorics Tree traversal symbols.namesake Artificial Intelligence Hardware and Architecture TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY symbols Algorithm Time complexity Software Mathematics |
| Zdroj: | Journal of Parallel and Distributed Computing. 27:100-105 |
| ISSN: | 0743-7315 |
| DOI: | 10.1006/jpdc.1995.1075 |
| Popis: | We consider the following problem. For a binary tree T = ( V , E ) where V = {1, 2, ..., n }, given its inorder traversal and either its preorder or its postorder traversal, reconstruct the binary tree. We present a new parallel algorithm for this problem. Our algorithm requires O ( n ) space. The main idea of our algorithm is to reduce the reconstruction process to merging two sorted sequences. With the best parallel merging algorithms, our algorithm can be implemented in O (log log n ) time using O ( n /log log n ) processors on the CREW PRAM (or in O (log n ) time using O ( n /log n ) processors on the EREW PRAM). Our result provides one more example of a fundamental problem which can be solved by optimal parallel algorithms in O (log log n )time on the CREW PRAM. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect