An Empirical Study of Insertion and Deletion in Binary Search Trees.
CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
This paper describes an experiment on the effect of insertions and deletions on the path length of unbalanced binary search trees. Given a random binary tree, repeatedly inserting and deleting nodes yields a tree that is no longer random. The expected internal path length differs when different deletion algorithms are used. Previous empirical studies indicated that expected internal path length tends to decrease after repeated insertions and asymmetric deletion. This study shows that performing a larger number of insertions and asymmetric deletion actually increases the expected internal path length, and that for sufficiently large trees, the expected internal path length becomes worse than that of a random tree. However, with a symmetric deletion algorithm, the results indicate that performing a large number of insertions and deletions decreases the expected internal path length, and that the expected internal path length remains better than that of a random tree. Author
- Theoretical Mathematics