カウントフィールドを持つ自己組織的2分探索木

福島　甫  木村　正行  

誌名
電子情報通信学会論文誌 D   Vol.J61-D   No.7   pp.473-480
発行日: 1978/07/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5713
論文種別: 論文
専門分野: 
キーワード: 


本文: PDF(720.6KB)>>
論文を購入



あらまし: 
各レコードの検索される確率が未知である場合に，検索を行いながら木のコストを低く保つように木自身の構造を変えていく自己組織的な2分探索木を考えることができる．本論文では，検索された回数を各レコードごとに記録し，それを用いて木の構造の修正を行う自己組織的な2分探索木，D-sobstを提案し，その性質などについて検討している．その結果，確率が定常であれば，D-sobstは準最適木の一つであるdescending treeに収束することが示される．又，そのときの収束の速さについて，十分な回数だけ検索されたD-sobstの振舞いを近似するモデルを用いて計算機実験を行い，必ずしも全部のレコードが検索されなくてもコストが十分に収束値に近づくことを明らかにしている．最後に実行時間についても検討し，D-sobstを表すデータ構造としていわゆるdoubly linked treeを採用すれば，通常の2分木探索アルゴリズムよりも実行時間を短縮できることを示している．