2分探索木を通りがけ順になぞる並列アルゴリズム
Bibliographic Information
- Other Title
-
- 2ブン タンサク ボク オ トオリガケ ジュン ニ ナゾ ルヘイレツ アルゴリズム
- Parallel Algorithm for Inorder Traversal of a Binary Search Tree
Search this article
Abstract
2分探索木を通りがけ順になぞる並列アルゴリズムを並列計算機モデルCREW PRAMのもとで提案する．このアルゴリズムでは，はじめにオイラーツアー技法を用いて2分探索木のオイラー閉路を求め，その走査リストから簡潔で効率良く通りがけ順の値を算定する並列アルゴリズムを示す．この並列アルゴリズムの時間計算量は，節点の数を $N$ とすると，$O(N)$ のプロセッサを用いて通りがけ順の値を $O(?log N)$ 時間で求めることができる．
We propose an efficient parallel algorithm to number the verticesin inorder on a binary search tree by using Euler tour technique.The proposed algorithm can be implemented in $O(\log N)$ time with $O(N)$ processors in CREW PRAM,provided that the number of nodes in the tree is $N$.
Journal
-
- 情報処理学会論文誌
-
情報処理学会論文誌 41 (10), 2941-2944, 2000-10-15
東京 : 情報処理学会
- Tweet
Keywords
Details 詳細情報について
-
- CRID
- 1050282812861944704
-
- NII Article ID
- 110002725533
-
- NII Book ID
- AN00116647
-
- ISSN
- 18827764
- 03875806
-
- NDL BIB ID
- 5530251
-
- Text Lang
- ja
-
- Article Type
- journal article
-
- Data Source
-
- IRDB
- NDL
- CiNii Articles