著者

右田 雅裕 中村 良三

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.41, no.10, pp.2941-2944, 2000-10-15

---

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$.