Abstract
In this paper we improve previous bounds on expected measures of AVL trees by using fringe analysis. A new way of handling larger tree collections that are not closed is presented. An inherent difficulty posed by the transformations necessary to keep the AVL tree balanced makes its analysis difficult when using fringe analysis methods. We derive a technique to cope with this difficulty obtaining the exact solution for fringe parameters even when unknown probabilities are involved. We show that the probability of a rotation in an insertion is between 0.37 and 0.73 (and seems to be less than 0.56), that the fraction of balanced nodes is between 0.56 and 0.78, and that the expected number of comparisons in a search seems to be at most 12% more than in the complete balanced tree.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
G. M. Adel'son-Vel'skii and E. M. Landis.An algorithm for the organization of information. Doklady Akademia Nauk SSSR, 146 (2): 263–266, 1962. English translation in Soviet Math. Doklady 3, 1962, 1259–1263.
A. C.-C. Yao.On random 2–3 trees. Acta Informatica, 9 (2): 159–170, 1978.
M. R. Brown.A partial analysis of random height-balanced trees. SIAM J on Computing, 8 (1): 33–41, Feb 1979.
K. Mehlhorn.A partial analysis of height-balanced trees. Technical Report A79/13, Universität des Saarlandes, Saarbrücken, West Germany, 1979.
Th. Ottmann and H. W. Six.Eine neue Klasse von ausgeglichenen Binärbäumen. Angewandte Informatik, 9: 395–400, 1976.
Thomas Ottmann and Derick Wood. 1–2brother trees or AVL trees revisited. Computer Journal, 23 (3): 248–255, Aug 1980.
Kurt Mehlhorn.A partial analysis of height-balanced trees under random insertions and deletions. SIAM J on Computing, 11 (4): 748–760, Nov. 1982.
Kurt Mehlhorn and A. Tsakalidis.An amortized analysis of insertions into AVL-trees. SIAM J on Computing, 15 (1): 22–33, Feb 1986.
B. Eisenbarth, N. Ziviani, Gaston H. Gonnet, Kurt Mehlhorn and Derick Wood.The theory of fringe analysis and its application to 2–3 trees and B-trees. Information and Control, 55 (1): 125–174, Oct 1982.
N. Ziviani.The Fringe Analysis of Search Trees. PhD thesis, Department of Computer Science, University of Waterloo, 1982.
R. A. Baeza-Yates and G. H. Gonnet.Average case analysis of algorithms using matrix recurrences. In 2nd International Conference on Computing and Information, ICCI'90, pages 47–51, Niagara Falls, Canada, May 1990. Also as Technical Report CS-89-16, Dept. of Computer Science, U. of Waterloo, 1989.
D.-E. Knuth.The Art of Computer Programing: Sorting and Searching, volume 3. Addison-Wesley, Reading, Mass., 1973.
D. E. Knuth.The Art of Computer Programming: Fundamental Algorithms, volume 1. Addison-Wesley, Reading, Mass., 1969.
N. Ziviani and F. W. Tompa.A look at symmetric binary B-trees. Infor, 20 (2): 65–81, May 1982.
Author information
Authors and Affiliations
Additional information
The work of the first author was also supported by the Institute for Computer Research of the University of Waterloo, the second author by a Natural Sciences and Engineering Research Council of Canada Grant No. A-3353, and the third by a Brazilian Coordenação do Aperfeiçoamento de Pessoal de Nível Superior Contract No. 4799/77 and by the University of Waterloo.