Ph. D. Thesis Abstract

The Effect of Asymmetric Deletions on Binary Search Trees

Joseph Culberson.

University of Waterloo Department of Computer Science, 1986.

This thesis deals with the study of binary search trees subjected to insertions and deletions using the standard Hibbard deletion scheme. It has been widely believed that deletions followed by insertions caused the internal path length of binary trees to be reduced on average. Recent empirical results obtained by Eppinger and Culberson cast doubt on this assumption. We present strong theoretical and empirical evidence that long sequences of deletion and insertion pairs result in trees with an expected internal path length of Theta(N^{3/2}). We also show that this theory applies to a wide variety of asymmetric deletion algorithms, including an improved one by Knuth.

We present the results of extensive simulations in an attempt to verify the estimates of the leading coefficient and lower order terms of the internal path length. A simulation of special features of trees provides results on trees as large as 100,000 nodes.

Finally, we consider the problem of designing deletion algorithms without using rebalancing techniques that yield good average case behavior.

joe@cs.ualberta.ca