文献

J-GLOBAL ID：201202255764169994   整理番号：12A0378994

AVL木の拡張とB木との比較評価

Evaluation for Comparison of Extended AVL Trees and B-Trees

著者 (2件)： 竹之下朗 (鹿児島大 理) ,  新森修一 (鹿児島大 大学院理工学研究科)
資料名： 鹿児島大学理学部紀要(Web)  (Reports of the Faculty of Science, Kagoshima University (Web))
巻： 44  ページ： 15-26 (WEB ONLY)  発行年： 2011年 
JST資料番号： U0191A  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 著者らは以前に2分探索木であるAVL木を文字列検索に適するように拡張し,データの比較において添字を戻さないために5分木に拡張したAVL木を提案した。本論文では,2分木の左部分木,右部分木,前部分木,中央部分木,後部分木を加えたデータ構造で文字列を配列で格納し,動的に挿入・削除できるようにリスト構造を用いる木構造で平衡化を行う拡張したAVL木を評価した。同様に平衡木で各節点が最大k(≧2)個の子を持てるB木は計算機の記憶領域で実用されており,1)データを木に挿入するのに要した時間,2)メモリ使用量,3)木の構築における比較回数,4)木に含まれないデータの探索時間,5)前記探索における比較回数を数値実験で比べた。その結果,先頭から後戻りすることなく,文字列を1桁ずつ比較する拡張したAVL木は3)がB木の11%となり,1)がB木の約47%,2)がB木の約36%となった。また,4)はB木の約55%,5)はB木の約1%となり,拡張したAVL木には多くの部分木があって対象の部分木に早く到達することがわかった。さらに,データ数nのときの拡張したAVLの計算量はnlogn+28nとなり,領域計算量を比較してn=10¹⁴以上ならばB木よりも領域が小さいことを示した。

シソーラス用語： *二分木 ,  *木探索 ,  木【グラフ】 ,  ツリー構造 ,  記憶容量 ,  可到達性 ,  *計算量 ,  アルゴリズム ,  性能評価
準シソーラス用語： *二分探索木 ,  AVL木 ,  B木

分類 (3件)： グラフ理論基礎  (IA02020S) ,  人工知能  (JE08000Z) ,  計算理論  (JB02000A)

タイトルに関連する用語 (4件)： 木 ,  拡張 ,  B木 ,  比較評価