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

• 右田, 雅裕

• 中村, 良三

書誌事項

タイトル別名

• 2ブン タンサク ボク オ トオリガケ ジュン ニ ナゾ ルヘイレツ アルゴリズム
• Parallel Algorithm for Inorder Traversal of a Binary Search Tree

抄録

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

収録刊行物

• 情報処理学会論文誌

  情報処理学会論文誌 41 (10), 2941-2944, 2000-10-15

  東京 : 情報処理学会

キーワード

• テクニカルノート

詳細情報

• CRID: 1050282812861944704
• NII論文ID: 110002725533
• NII書誌ID: AN00116647
• ISSN: 18827764
• ISSN: 03875806
• NDL書誌ID: 5530251
• Web Site: http://id.nii.ac.jp/1001/00012178/
• Web Site: https://ndlsearch.ndl.go.jp/books/R000000004-I5530251
• 本文言語コード: ja
• 資料種別: journal article
• データソース種別:
  • IRDB
  • NDL
  • CiNii Articles