Observations on the Performance of AVL Trees,
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 01, 1973
- Accession Number
- AD0766323
Entities
People
- E. B. Kaehler
- P. L. Karlton
- R. E. Scroggs
- S. H. Fuller
Organizations
- Carnegie Mellon University