An Approximate Analysis of the AVL Balanced Tree Insertion Algorithm(<特集>Special Issue on Generation Database Technology for Internet, Multimedia and Mobile computing)

概要

論文の詳細を見る
Two particularly interesting questions concerning the performance of the AVL balanced tree insertion algorithm are: i)If all n! permutations of n keys occur with equal probability, what is the expected height of the constructed AVL balanced tree? ii)What is the probability that an insertion requires rebalancing? Although some empirical results about the expected height of the AVL balanced tree and the probability that an insertion requires rebalancing have been obtained, the mathematical analysis of these two problems is still open. In order to analyze both of these questions we should grasp the characters of the AVL balanced tree structures. In this paper, as the first step toward the analysis of these two open problems, we assume that all AVL balanced trees with the given number of nodes and height are constructed with equal probability instead of the hypothesis that all n! permutations of n keys occur with equal probability. Based on this assumption, we first derive a formula to enumerate the different AVL balanced trees with n internal nodes and height h. Then, we propose the formulae to evaluate the expected height of the AVL balanced tree and the probability that an insertion requires rebalancing. The results from these proposed formulae are very close to those empirical ones obtained so far.
一般社団法人情報処理学会の論文
1998-04-15