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

概要

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