http://swrc.ontoware.org/ontology#UnrefereedArticle
AVL木の拡張とB木との比較評価
ja
data structure
AVL trees
computational complexity
竹之下 朗
新森 修一
In this paper, we propose to develop an extended AVL tree with 5-subtrees, for the purpose of increasing search efficiency, and examine various evaluations for the extended AVL tree. The data structure of this extended AVL tree contains 5 partially balanced subtrees that match prefixes character by character by implementing the radix search method. A numerical experiment confirmed that the construction time was about 50% of B-tree. When the height of B-trees is smallest, the amount of memory becomes smaller than that of B-trees, using 10^{14} pieces of data or more. The construction time of the extended AVL trees was about 47% of that of B-trees in a numerical experiment using 10 million random pieces with 100-digit character strings in the decimal number, and the comparison frequency of the extended AVL trees obtained an excellent result of about 11% of that of B-trees. In this case, the amount of memory became about 36% for that of B-trees.
鹿児島大学理学部紀要=Reports of the Faculty of Science, Kagoshima University
44
15-26
13456938
AA11246904
007
鹿児島大学
論文(Article)