作成者 |
|
|
|
本文言語 |
|
出版者 |
|
|
発行日 |
|
収録物名 |
|
巻 |
|
号 |
|
開始ページ |
|
終了ページ |
|
出版タイプ |
|
アクセス権 |
|
JaLC DOI |
|
関連DOI |
|
関連URI |
|
関連情報 |
|
概要 |
Many algorithms have been presented for constructing a binary tree from its traversals. This problem can be solved by a sequential algorithm of linear time, such as E. Makinen's and A. Andersson and S.... Carlsson's algorithms. If the number of comparison operations is used as a measure of time complexity, the linear coefficient of E. Makinen's is 3 in its best case and 5 in its worst case, and that of A. Andersson and S. Carlsson's is 4 in its best case and 7 in its worst case. In this article, we give a more efficient sequential algorithm for the problem, and the linear coefficient is 3 in any case.続きを見る
|