IEICE Trans - 平衡2分探索木に対する並列オンライン操作

平衡2分探索木に対する並列オンライン操作

柘植　宗俊   藤本　典幸   萩原　兼一

誌名
電子情報通信学会論文誌 D   Vol.J80-D1       pp.582-590
発行日: 1997/07/25
Online ISSN:
DOI:
Print ISSN: 0915-1915
論文種別: 専門分野: アルゴリズム，計算複雑性
キーワード:
平衡2分探索木,  パイプライン化,  中間順,  オンライン実行,  遅延削除,

本文: PDF(653.4KB)>>

あらまし:
本論文では，平衡2分探索木に対する要素の挿入，検索，および削除といった操作が任意の順序で次々と与えられたときに，この入力操作系列をオンライン実行するためのパイプライン処理を用いた並列アルゴリズムを提案する．特に，今まで効率の良いパイプライン化が難しいとされてきた平衡2分探索木の要素の削除アルゴリズム，および2分探索木の平衡化アルゴリズムを提案する．これらのアルゴリズムでは遅延削除（lazy deletion）と呼ばれる手法を用いて要素の削除を行う．すなわち，各頂点にデータが有効であるかどうかを示すフラグを設け，削除アルゴリズムではそのフラグを操作する．そしてある程度の長さの操作系列を実行した後，このフラグで有効なデータのみの中間順（in-order）の値を計算し，この値を用いて平衡化を行う．この削除と平衡化の手法を用いて，頂点数nの平衡2分探索木に対する長さO（log n）の任意の操作系列をパイプライン化して並列実行し，その後に2分探索木の平衡化を行い平衡2分探索木を得るまでを，EREW PRAM計算モデルにおいて時間O（log n），総命令数O（n）で実行できることを示す．