Home Table of Contents News Blogs Opinion Research Practice Contributed Articles Review Articles Careers Archive Videos About Communications
Sign In
advertisement

Home → Magazine Archive → September 1983 (Vol. 26, No. 9) → An empirical study of insertion and deletion in binary... → Abstract

An empirical study of insertion and deletion in binary search trees

By Jeffrey L. Eppinger

Communications of the ACM, Vol. 26 No. 9, Pages 663-669
10.1145/358172.358183

This paper describes an experiment on the effect of insertions and deletions on the path length of unbalanced binary search trees. Repeatedly inserting and deleting nodes in a random binary tree 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 deletions. This study shows that performing a larger number of insertions and asymmetric deletions 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. With a symmetric deletion algorithm, however, the experiments 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.

The full text of this article is premium content

0 Comments

No entries found