Observations on the Performance of AVL Trees,

摘要

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 30nodes. 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.78nodes are revisited to restore the AVL property on insertion,and 1.91nodes 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)