2分探索木を通りがけ順になぞる並列アルゴリズム

IPSJ Web Site 5 References

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

References(5)*help

See more

Keywords

Details 詳細情報について

Report a problem

Back to top