Accession Number : AD0766323

Title :   Observations on the Performance of AVL Trees,

Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Scroggs,R. E. ; Karlton,P. L. ; Fuller,S. H. ; Kaehler,E. B.

Report Date : JUL 1973

Pagination or Media Count : 23

Abstract : The paper presents the results of a series of simulations that investigate the performance of AVL trees. It is shown that the only statistic of AVL trees that is a function of the size of the tree is the time to search for an item in the tree; the performance of all other procedures for maintaining AVL trees are independent of the size of the tree for trees greater than 30 nodes. In particular it was discovered that an average of .465 restructures are required per insertion and .214 restructures per deletion. Moreover, the average of 2.78 nodes are revisited to restore the AVL property on insertion, and 1.91 nodes are revisited on deletion. Actual timings of the AVL procedures for insertion, searching, and deletion are presented to provide a practical guide to estimating the cost of using AVL trees. (Author)

Descriptors :   (*SEARCH THEORY, *MATHEMATICAL LOGIC), COMPUTER PROGRAMMING, GRAPHICS, STATISTICAL ANALYSIS

Subject Categories : Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE